Simple Summary Paratuberculosis or Johne’s disease (JD) in cattle is a chronic granulomatous gastroenteritis caused by infection with Mycobacterium avium subspecies paratuberculosis (MAP). JD is not treatable; therefore, the early identification of infected animals is a key point in reducing its incidence worldwide. In this paper, combinatorial discriminant analysis was applied to transcriptomic data to find a small set of differentially expressed genes able to discriminate between exposed cattle from non-exposed animals. Results of the discriminant analysis identified 10 transcripts that differentiate between ELISA-negative animals belonging to paratuberculosis-positive herds that were potentially exposed to MAP and negative-unexposed animals belonging to paratuberculosis-negative herds. The 10 transcript signature was also used for the classification of 5 cattle positive-for-MAP infection samples, with the underlying hypothesis that their transcriptional profile should be closer to potentially exposed animals than to controls. The same set of 10 transcripts was able to differentiate ELISA-negative unexposed animals from positive animals based on the results of the ELISA test for bovine paratuberculosis and faecal culture. In conclusion, these findings suggest the possible use of the identified RNA expression signature as a new diagnostic test for paratuberculosis. Abstract Paratuberculosis or Johne’s disease in cattle is a chronic granulomatous gastroenteritis caused by infection with Mycobacterium avium subspecies paratuberculosis (MAP). Paratuberculosis is not treatable; therefore, the early identification and isolation of infected animals is a key point to reduce its incidence. In this paper, we analyse RNAseq experimental data of 5 ELISA-negative cattle exposed to MAP in a positive herd, compared to 5 negative-unexposed controls. The purpose was to find a small set of differentially expressed genes able to discriminate between exposed animals in a preclinical phase from non-exposed controls. Our results identified 10 transcripts that differentiate between ELISA-negative, clinically healthy, and exposed animals belonging to paratuberculosis-positive herds and negative-unexposed animals. Of the 10 transcripts, five ( TRPV4 , RIC8B , IL5RA , ERF , CDC40 ) showed significant differential expression between the three groups while the remaining 5 ( RDM1 , EPHX1 , STAU1 , TLE1 , ASB8 ) did not show a significant difference in at least one of the pairwise comparisons. When tested in a larger cohort, these findings may contribute to the development of a new diagnostic test for paratuberculosis based on a gene expression signature. Such a diagnostic tool could allow early interventions to reduce the risk of the infection spreading.