Paratuberculosis, caused by Mycobacterium avium subsp. paratuberculosis (Map), is a chronic granulomatous enteritis which primarily affects domestic and wild ruminants, resulting in serious economic losses for dairy and beef industry around the world. There is no satisfactory cure or vaccine, and actual diagnostic tests need improvement, particularly for the initial stages of the disease. Map specific cell-mediated immune responses may allow early detection of the infection at subclinical stages. In this study, over a period of 39 months, we collected 548 blood samples in two culture-confirmed Map-infected herds, 95 blood samples in five dairy herds that scored negative during 3 consecutive years of Map serology testing and 79 samples in three culture-confirmed M. bovis infected herds. Based on criteria of bacteriology, serology and ratio of IFN-γ induced with bovine and avian purified protein derivative of tuberculin (PPD-B/PPD-A), we classified the samples in four groups: 415 samples as Map-exposed/infected (MAP), 58 samples as aspecific reactors (AR), 179 samples as non-responders (NI) and 70 samples as M. bovis infected (TB). Age of the animals influenced the IFN-γ response in the MAP group, with PPD specific IFN-γ levels (but not PPD-B/PPD-A IFN-γ ratio) being significantly higher in animals <18 months of age. Map specific antibodies were detected by IDEXX ELISA in 13/415 (3%) sera of the MAP group, whereas fecal culture was positive for only 7/405 (1.7%) samples. Animals in the MAP group could therefore be considered being at the very early stage of Map infection. Six purified, recombinant Map antigens (Ag5, Ag6, MAP1637c, MAP0388, MAP3547c and MAP0586c), previously identified using combined advanced proteomic or reverse genomic approaches, were tested for their diagnostic potential in a 20h IFN-γ release assay. In the age group >18 months old, Ag5 and MAP0388 were recognized by only 10.1% and 7.7% of the animals in the MAP group, whereas a total of 38.6.%, 29.4%, 25.6% and 39.0% of the animals in the MAP group reacted to Ag6, MAP1637c, MAP3547c and MAP0586c respectively. None of the animals in the TB group reacted to Ag6, MAP1637c or MAP586c. Except for MAP0388, the % of reactors in the MAP group was significantly higher in animals <18 months old: 28.0%, 24.0%, 45.5%, 47.1%, 49.8% and 47.4% respectively. Further studies of these candidates and their combination are needed to confirm their diagnostic potential for the detection of early Map infection.