The effects of infection by Mycobacterium avium paratuberculosis (Map) on dairy cows are poorly documented and quite controversial. This retrospective study aimed at quantifying the variation in non-return to service of Holstein dairy cows according to their Map-infection status. Three different statuses were defined based on both individual and herd tests results: ELISA positive cow, all tests negative cow in a negative herd and all tests negative cow in a positive herd. Whatever the age at Map testing, the status was attributed to a cow from its first lactation onwards. Non-return to service was determined at 200 days after first and second services. The study was performed from 1999 to 2007 on 185,950 AI from 48,914 cows in early stage of the infection in 1069 herds by logistic regression controlling for known factors influencing non-return rate. Non-return rate was higher for infected cows compared to negative cows from negative herds (RR of 1.10 or +3.9 points of % of non-return rate). The effect was significant for parities 1 and 2 (RR of 1.11 and 1.12, respectively) but not for higher ones. This effect was lower when comparing positive cows to negative cows in the same herds but relative risks were still above 1. The hypothesis that the effect of Map on non-return depends upon the stage of infection is formulated.