Mycobacterium avium subspecies paratuberculosis (Mycobacterium paratuberculosis), the causative agent of paratuberculosis (paraTB) or Johne's disease in ruminants, is a health problem for the global cattle industry with significant economic losses related to decreased milk production and reduced fertility. Commonly paraTB in cattle is diagnosed by antibody detection by serum enzyme-linked immunosorbent assay (ELISA), by detection of the pathogen by cultivation of individual faecal samples, or by in vitro measurement of cell mediated immune responses using the IFN-gamma test. There is an ongoing need for developing new diagnostic approaches as all currently available diagnostic tests for paraTB may fail to detect sub-clinical infection. We used cDNA microarrays to simultaneously measure expression of over 1300 host genes to help identify a subset of gene expression changes that might provide a unique gene expression signature for paraTB infection. In the present study, non-stimulated leukocytes isolated from 10 sub-clinical paraTB infected cows were examined for genes being expressed at significantly different levels than in similar cells from control cows with the same herd background. We included cattle (Holstein) from two locations (Denmark and USA) for the microarray experiment. Our results indicate that expression profiles of at least 52 genes are different in leukocytes from M. paratuberculosis infected cattle compared to control cattle. Gene expression differences were verified by quantitative real-time reverse transcriptase polymerase chain reactions (qRT-PCR) on the same group of cattle (Holstein) used for the microarray experiment. In order to assess the generality of the observed gene expression, a second and different group of cattle (Jersey) was also examined using qRT-PCR. Out of the seven genes selected for qRT-PCR, CD30 ligand (CD30L) and P-selectin were consistently differentially expressed in freshly isolated leukocytes from paraTB infected and control animals of both breeds of cattle. Although further work is clearly needed to develop a more complete gene expression signature specific for paraTB, our results demonstrate that a subset of genes in leukocytes are consistently expressed at different levels, depending upon M. paratuberculosis infection status.