Background: Nigeria has the fourth highest tuberculosis (TB) burden worldwide. In this study, mycobacterial agents from clinically symptomatic TB patients, regardless of HIV co-infection were isolated and characterized, and resistance to isoniazid and rifampicin determined. Methods: Suspected TB cases were recruited from two TB clinics into a cross-sectional study. All patients were screened for HIV, and their sputum samples were screened for Mycobacteria using an algorithm that included smear microscopy, liquid broth and solid media culture, TB-antigen detection assay, and molecular probe assays, to determine the type of Mycobacterium and pattern of resistance to isoniazid and rifampicin. Results: Of 1,603 patients screened, 466 (29%) had liquid broth culture-positive pulmonary Mycobacterial infection. Of these, 444 (95%) had mycobacterial infections and 22 (5%) were false-positive non-mycobacterial strains. Of the 444 cases, 375 (80%) were infected with Mycobacterial tuberculosis (MTB) complex (354 M. tuberculosis, 1 M. bovis and 20 M. africanum) and 69 (15%) were Non-tuberculous mycobacteria (NTM). HIV co-infection was detected in 101 (27%) of the MTB complex and 26 (38%) of the NTM cases respectively. Twenty-three (6.1%) of the MTB complex cases had organisms resistant to isoniazid (3.5%), rifampicin (1.3%) or both, i.e. multi-drug resistant TB (MDR-TB, 1.3%), by molecular analysis, and of those, 8 (35%) had a prior history of TB treatment. Currently available molecular assays are incapable of detecting drug-resistant NTM strains. After controlling for prior treatment, cases with any resistance (i.e. at least to one drug) were more likely to be co-infected with HIV compared to cases without any resistance (OR=3.6, 95%CI=1.5-8.8; p=0.0039). Compared to M. tuberculosis, the NTM cases were more likely to be HIV co-infected more likely to present with clinical symptoms during the intense Harmattan dust storms from December to February (OR=2.5, 95%CI=1.4-4.5; p=0.0034, and OR=2.2, 95%CI=1.2-3.8; p<0.0067 and respectively), and less likely to be detected by the routine sputum smear test (OR=0.05, 95%CI=0.02-0.13; p<.0001). Conclusions: The high frequency of smear-negative NTM cases with HIV co-infection identified during the period of Harmattan dust storm presents a novel public health challenge. Introduction of molecular detection assays to identify smear-negative NTM and MDR-TB is a high priority.