Colonization of multidrug resistant (MDR) bacteria is associated with subsequent invasive infections in children with comorbidities. This study aimed to determine the resistance profile and factors associated with MDR pathogen colonization among HIV−and HIV+ children below five years of age in Mwanza, Tanzania. A total of 399 (HIV− 255 and HIV+ 144) children were enrolled and investigated for the presence of MDR bacteria. The median [IQR] age of children was 19 (10–36) months. Out of 27 Staphylococcus aureus colonizing the nasal cavity, 16 (59.5%) were methicillin resistant while 132/278 (47.2%) of Enterobacteriaceae from rectal swabs were resistant to third generation cephalosporins, with 69.7% (92/132) exhibiting extended spectrum beta lactamase (ESBL) phenotypes. The proportion of resistance to gentamicin, amoxicillin/clavulanic acid and meropenem were significantly higher among HIV+ than HIV− children. A history of antibiotic use in the last month OR 2.62 [1.1, 6.9] (p = 0.04) and history of a relative admitted from the same household in the past three months OR 3.73 [1.1, 13.2] (p = 0.03) independently predicted ESBL rectal colonization. HIV+ children had significantly more fecal carriage of isolates resistant to uncommonly used antibiotics. There is a need to strengthen antimicrobial stewardship and Infection Prevention and Control (IPC) programs to prevent the emergence and spread of MDR pathogens in children.