In children, Mycobacterium tuberculosis (M. tuberculosis) frequently disseminates systemically, presenting with nonspecific signs including fever. We determined prevalence of M. tuberculosis bacteremia among febrile children presenting to hospitals in Nyanza, Kenya (a region with high human immunodeficiency virus (HIV) and M. tuberculosis prevalence). Between March 2013 and February 2014, we enrolled children aged 6 months to 5 years presenting with fever (axillary temperature ≥ 37.5°C) and no recent antibiotic use. Blood samples were collected for bacterial and mycobacterial culture using standard methods. Among 148 children enrolled, median age was 3.1 years (interquartile range: 1.8–4.1 years); 10.3% of children were living with a household member diagnosed with M. tuberculosis in the last year. Seventeen percent of children were stunted (height-for-age z-score < −2), 18.6% wasted (weight-for-height z-score < −2), 2.7% were HIV-infected, and 14.2% were HIV-exposed uninfected. Seventeen children (11.5%) had one or more signs of tuberculosis (TB). All children had a Bacille Calmette-Guerin vaccination scar. Among 134 viable blood cultures, none (95% confidence interval: 0–2.7%) had Mycobacterium isolated. Despite exposure to household TB contacts, HIV exposure, and malnutrition, M. tuberculosis bacteremia was not detected in this pediatric febrile cohort, a finding consistent with other pediatric studies.