With the rising number of patients with human immunodeficiency virus (HIV)/AIDS in developing countries, the control of mycobacteria is of growing importance. Previous studies have shown that rodents and insectivores are carriers of mycobacteria. However, it is not clear how widespread mycobacteria are in these animals and what their role is in spreading them. Therefore, the prevalence of mycobacteria in rodents and insectivores was studied in and around Morogoro, Tanzania. Live rodents were trapped, with three types of live traps, in three habitats. Pieces of organs were pooled per habitat, species, and organ type (stratified pooling); these sample pools were examined for the presence of mycobacteria by PCR, microscopy, and culture methods. The mycobacterial isolates were identified using phenotypic techniques and sequencing. In total, 708 small mammals were collected, 31 of which were shrews. By pool prevalence estimation, 2.65% of the animals were carriers of mycobacteria, with a higher prevalence in the urban areas and in Cricetomys gambianus and the insectivore Crocidura hirta. Nontuberculous mycobacteria (Mycobacterium chimaera, M. intracellulare, M. arupense, M. parascrofulaceum, and Mycobacterium spp.) were isolated from C. gambianus, Mastomys natalensis, and C. hirta. This study is the first to report findings of mycobacteria in African rodents and insectivores and the first in mycobacterial ecology to estimate the prevalence of mycobacteria after stratified pool screening. The fact that small mammals in urban areas carry more mycobacteria than those in the fields and that potentially pathogenic mycobacteria were isolated identifies a risk for other animals and humans, especially HIV/AIDS patients, that have a weakened immune system.