Paratuberculosis is an incurable disease in ruminants with great worldwide economic impact, caused by Mycobacterium avium subsp. paratuberculosis (MAP). The objective of this study was to carry out a study of the molecular epidemiology of the MAP using the restriction enzyme analysis (REA) technique of IS1311 MAP region in biological samples of feces, intestinal tissue, and mesenteric lymph nodes of cattle and buffaloes from six Brazilian states. In total, 109 samples of feces and tissues of cattle and buffaloes were collected from animal paratuberculosis suspected. Twenty-five samples were positive in the detection of the DNA of the IS900 region of MAP and it was possible to type 18 strains in the analysis of the region IS1311, being 100% of them identified as belonging to subtype Bison MAP strain. This is the first epidemiological molecular study of MAP in Brazil. The results indicate that paratuberculosis is widespread in cattle and in buffaloes in several regions of Brazil, and the subtype Bison MAP strain was the only one identified in the samples analyzed in this study, demonstrating the similarity between the strains from different states tested. These results provide the necessary support for the implementation of paratuberculosis control strategies in cattle and buffaloes in Brazil.