Mycobacterium tuberculosis, the causative agent of tuberculosis in humans, is considered primarily a human pathogen. It has, however, been reported in a wide range of domestic and wild animals, often living in close prolonged contact with humans. Sputum samples in which acid fast bacteria were detected in smears were collected from patients at three health facilities in Namwala district, Zambia. Samples from cattle presenting gross lesions compatible with bovine tuberculosis were collected at a local abattoir in the same district. Isolated mycobacteria were identified and genotyped using classical molecular methods. From a total of 33 isolates of M. tuberculosis detected (30 from humans and 3 from cattle), two cattle isolates shared the same spoligotype and MIRU-VNTR pattern with a human patient. This study has for the first time documented the isolation of M. tuberculosis from cattle in Zambia and provides molecular evidence of an epidemiological link between M. tuberculosis isolates from humans and cattle in Namwala district. A possible spill back of M. tuberculosis to humans cannot be excluded and therefore further studies documenting to what extent M. tuberculosis is shed in cattle milk are needed. This finding further suggests that veterinary public health measures to control human TB, should also take into account the bovine reservoir.