Emergence and spread of extended spectrum beta-lactamase (ESBL)-producing gram-negative bacteria, mainly due to CTX-M, is a major global public health problem. Patients infected with ESBL-producing gram-negative bacteria have an increased risk of treatment failure and death. We investigated the prevalence and risk factors for CTX-M gram-negative bacteria isolated from clinical specimens of patients hospitalized at a tertiary care hospital in Kilimanjaro, Tanzania. Isolated gram-negative bacteria from inpatients admitted at Kilimanjaro Christian Medical Centre (KCMC) between August 2013 and August 2015 were fully genome sequenced. The prevalence of ESBL-producing gram-negative bacteria was determined based on the presence of blaCTX-M. The odds ratio (OR) and risk factors for ESBL-producing gram-negative bacteria due to CTX-M were assessed using logistic regression models. The overall CTX-M prevalence (95% CI) was 13.6% (10.1–18.1). Adjusted for other factors, the OR of CTX-M gram-negative bacteria for patients previously hospitalized was 0.26 (0.08–0.88), p = 0.031; the OR for patients currently on antibiotics was 4.02 (1.29–12.58), p = 0.017; the OR for patients currently on ceftriaxone was 0.14 (0.04–0.46), p = 0.001; and the OR for patients with wound infections was 0.24 (0.09–0.61), p = 0.003. The prevalence of ESBL-producing gram-negative bacteria due to CTX-M in this setting is relatively low compared to other previous reports in similar settings. However, to properly stop further spread in the hospital, we recommend setting up a hospital surveillance system that takes full advantage of the available next-generation sequencing facility to routinely screen for all types of bacterial resistance genes.