Culture is considered the definitive technique for Johne's disease diagnosis, and it is essential for later applications of certain molecular typing techniques. In this study, we have tested four solid media (Herrold's egg yolk medium [HEYM] with sodium pyruvate and mycobactin [HEYMm-SP], HEYM with mycobactin and without sodium pyruvate [HEYMm], Middlebrook 7H11 with mycobactin [Mm], and Löwenstein-Jensen with mycobactin [LJm]) for isolation of Mycobacterium avium subsp. paratuberculosis strains in 319 tissue samples from cattle herds and goat flocks. We have shown that each of the two main groups of M. avium subsp. paratuberculosis (type II and type I/III) has different requirements for growth in the culture media studied. The recommended solid media for isolation of type I/III strains are LJm and Mm, since the combination of both media allowed the recovery of all these strains. The most widespread culture medium, HEYM, is not suitable for the isolation of this group of M. avium subsp. paratuberculosis strains. Regarding the type II strains, HEYMm-SP was the medium where more strains were isolated, but the other three media are also needed in order to recover all type II strains. The incubation period is also related to the strain type. In conclusion, because the type of strain cannot be known in advance of culture, coupled with the fact that cattle and goats can be infected with both groups of strains, we recommend the use of the four solid media and the prolongation of the incubation period to more than 6 months to detect paratuberculous herds/flocks and to determine the true prevalence of the infection.