Between 1982 and 2000, fecal samples were obtained from 786 cows that were shedding Mycobacterium avium subsp. paratuberculosis (Map). These cows were resident on 93 Pennsylvania dairies (mean herd size, 64 milk cows) that had no or minimal previous testing for Map. Feces were cultured on four tubes of Herrold's egg yolk medium and the distribution of mean Map colony forming units (CFU) was evaluated. Most cows were light (< 10 CFU/tube, 51.4%) or high (> 50 CFU/tube, 30.8%) fecal shedders with fewer cows in the moderate category (10-50 CFU/tube). Of the 786 cows, 192 (24.4%) had colonies in only one of four tubes. In the multivariable negative binomial model, there were significant associations between mean CFU/tube and prevalence, herd size, and season and an interaction between herd size and season. The linear mixed model of continuous tube counts with a random herd effect yielded similar findings with associations with herd size as a continuous variable, season, and an interaction between categorized prevalence and continuous herd size. Variability in CFU/tube was greatest among cows in the same herd, intermediate for replicate tubes from the same cow, and smallest among cows in different herds. Reduction in the number of replicate tubes from four would have reduced the sensitivity of fecal culture for Map by approximately 6% (for three tubes) to 12% (for two tubes).