Invasive Non-typhoidal Salmonella (iNTS) disease is a major public health challenge, especially in Sub-Saharan Africa (SSA). In Kenya, mortality rates are high (20-25%) unless prompt treatment is instituted. The most common serotypes are Salmonella enterica serotype Typhimurium (S. Typhimurium) and Salmonella enterica serotype Enteritidis (S. Enteritidis). In a 5 year case-control study in children residing in the Mukuru informal settlement in Nairobi, Kenya, a total of 4201 blood cultures from suspected iNTS cases and 6326 fecal samples from age-matched controls were studied. From the laboratory cultures we obtained a total of 133 S. Typhimurium isolates of which 83(62.4%) came from cases (53 blood and 30 fecal) and 50(37.6%) from controls (fecal). A total of 120 S. Enteritidis consisted of 70(58.3%) from cases (43 blood and 27 fecal) and 50(41.7%) from controls (fecal). The S. Typhimurium population fell into two distinct ST19 lineages constituting 36.1%, as well as ST313 lineage I (27.8%) and ST313 lineage II (36.1%) isolates. The S. Enteritidis isolates fell into the global epidemic lineage (46.6%), the Central/Eastern African lineage (30.5%), a novel Kenyan-specific lineage (12.2%) and a phylogenetically outlier lineage (10.7%). Detailed phylogenetic analysis revealed a high level of relatedness between NTS from blood and stool originating from cases and controls, indicating a common source pool. Multidrug resistance was common throughout, with 8.5% of such isolates resistant to extended spectrum beta lactams. The high rate of asymptomatic carriage in the population is a concern for transmission to vulnerable individuals and this group could be targeted for vaccination if an iNTS vaccine becomes available.