The objective of this study was the serological, bacteriological and molecular diagnosis, as well as the molecular characterization of Mycobacterium avium subsp. paratuberculosis (Map) in adult cows of five Colombian dairy herds. Serum samples were tested by an indirect absorbed enzyme-linked immunosorbent assay (ELISA-C). All fecal samples were tested by pooled culture. After that, fecal samples of Map positive pools were tested individually by culture and polymerase chain reaction (PCR). In one herd, slurry and tissue samples from one animal were also taken and tested by PCR and culture. Map isolates were analyzed by the Multilocus Short Sequence Repeat (MLSSR) and the Mycobacterial Interspersed Repetitive Units-Variable Number of Tandem Repeats (MIRU-VNTR) methods. ELISA produced positive results in 1.8% (6/329) of the animals and 40% (2/5) of the herds. Four fecal, two tissue, and two slurry samples from a herd were Map positive by culture and PCR. MLSSR and MIRU-VNTR revealed two different strain profiles among eight Map isolates recovered. This study reports the first molecular characterization of Map in one dairy herd in Colombia, the limitations for individual diagnosis of subclinical Map infections in cattle, and the usefulness of pooled fecal samples and environmental sampling for Map diagnosis.