Johne’s Disease (JD), a ruminant infectious disease caused by Mycobacterium avium subspecies paratuberculosis (MAP), is characterized by a long latent period followed by an aggressive acute phase in which the animal experiences diarrhea and extreme wasting. The absence of symptoms and low levels of bacterial shedding during the latent period make early diagnosis difficult. We analyzed the expression profiles of 34 samples of ileocecal valve (ICV, site of infection) and associated lymph node (LN) from 14 mature cows with naturally acquired JD to determine whether gene expression patterns could differentiate control, sub-clinical and clinical states. Transcriptome sequencing (RNA-seq) was carried out using the Illumina DSN protocol to detect low abundance transcripts. 530 million reads were aligned to the bovine and MAP genomes. MAP reads in ICV increased roughly in parallel with disease state. Bovine read count-based expression values normalized using the TMM method to minimize non-disease effects. Differential expression analysis was carried out in JMP Genomics 5.1. Unique sequence-based molecular signatures of gene expression were developed for each JD stage and tissue-type and robust comparisons made between control vs. sub-clinical (ICV: n=20; LN: n=13); sub-clinical vs. clinical (ICV: n=63, LN: n=25); and control vs. clinical (ICV: n=110; LN: n=87). Transcript profiles were related to increased inflammatory responses, metabolic and mitochondrial perturbations. Significant differences identified between control and sub-clinical samples may represent early markers for disease. The unique gene signatures potentially provide insights into JD pathogenesis, aid in timely diagnosis and identify candidate targets and pathways for therapeutic intervention.