Mycobacterium avium subsp. paratuberculosis (MAP) is the causative agent of Johne's disease (JD), a chronic intestinal inflammatory disease of cattle and other ruminants. JD has a high herd prevalence and causes serious animal health problems and significant economic loss in domesticated ruminants throughout the world. Since serological detection of MAP infected animals during the early stages of infection remains challenging due to the low sensitivity of extant assays, we screened 180 well-characterized serum samples using a whole proteome microarray from Mycobacterium tuberculosis (MTB), a close relative of MAP. Based on extensive testing of serum and milk samples, fecal culture and qPCR for direct detection of MAP, the samples were previously assigned to one of 4 groups: negative low exposure (n = 30, NL); negative high exposure (n = 30, NH); fecal positive, ELISA negative (n = 60, F+E-); and fecal positive, ELISA positive (n = 60, F+E+). Of the 740 reactive proteins, several antigens were serologically recognized early but not late in infection, suggesting a complex and dynamic evolution of the MAP humoral immune response during disease progression. Ordinal logistic regression models identified a subset of 47 candidate proteins with significantly different normalized intensity values (p<0.05), including 12 in the NH and 23 in F+E- groups, suggesting potential utility for the early detection of MAP infected animals. Next, the diagnostic utility of four MAP orthologs (MAP1569, MAP2942c, MAP2609, and MAP1272c) was assessed and reveal moderate to high diagnostic sensitivities (range 48.3% to 76.7%) and specificity (range 96.7% to 100%), with a combined 88.3% sensitivity and 96.7% specificity. Taken together, the results of our analyses have identified several candidate MAP proteins of potential utility for the early detection of MAP infection, as well individual MAP proteins that may serve as the foundation for the next generation of well-defined serological diagnosis of JD in cattle.