The objective was to evaluate the survival of Mycobacterium paratuberculosis (Map) in naturally infected dairy cows feces under long periods of freezing at -18°C and -70°C. Samples were collected from cows previously tested positive with serum ELISA or fecal culture, or with clinical signs of Johne's disease. Samples were stored at -18C and/or -70°C and recultured in Herrold's egg yolk media every 36 months. A proportional odds mixed model was used for data analysis. Sixty nine fecal samples were stored for different periods between September 2002 and January 2005. Of these, 45 (65) were stored at -18°C and 24 (35) at -70°C. Average number of days between repeated culture dates was 98 and 84 for -18C and -70C, respectively. Median number of repeated cultures was 6 and 4 for samples stored at -18°C and -70°C, respectively. After adjusting for initial sample bacterial load, the effects of temperature or number of thawing and refreezing cycles on Map viability were not significant. The probability that a sample decreases from high to moderate-low bacterial load and from moderate-low to negative bacterial load was 13.5 per month. Although this study found gradual reduction of Map concentration in stored fecal samples through time, overall survival in -18°C can ease fecal samples management in laboratories with low-processing capacity or lack of -70°C freezer.