Johne’s disease, caused by Mycobacterium avium subsp. paratuberculosis (MAP), causes weight loss, diarrhoea, and reduced milk yields in clinically infected cattle. Asymptomatic, subclinically infected cattle shed MAP bacteria but are frequently not detected by diagnostic tests. Herein, we compare the metabolite profiles of sera from subclinically infected Holstein–Friesian heifers and antibody binding to selected MAP antigens. The study used biobanked serum samples from 10 naturally MAP-infected and 10 control heifers, sampled monthly from ~1 to 19 months of age. Sera were assessed using flow infusion electrospray–high-resolution mass spectrometry (FIE–HRMS) on a Q Exactive hybrid quadrupole–Orbitrap mass spectrometer for high-throughput, sensitive, non-targeted metabolite fingerprinting. Partial least-squares discriminant analyses (PLS-DA) and hierarchical cluster analysis (HCA) of the data discriminated between naturally MAP-infected and control heifers. In total, 33 metabolites that differentially accumulated in naturally MAP-infected heifers compared to controls were identified. Five were significantly elevated within MAP-infected heifers throughout the study, i.e., leukotriene B4, bicyclo prostaglandin E2 (bicyclo PGE2), itaconic acid, 2-hydroxyglutaric acid and N6-acetyl-L-lysine. These findings highlight the potential of metabolomics in the identification of novel MAP diagnostic markers and particular biochemical pathways, which may provide insights into the bovine immune response to MAP.