Background Non-typhoidal Salmonella (NTS) serotypes Typhimurium and Enteritidis are a major cause of bloodstream infections in children in sub-Saharan Africa but their reservoir is unknown. We compared pairs of NTS blood and stool isolates (with the same NTS serotype recovered in the same patient) for genetic similarity. Methods Between November 2013 and April 2017, hospital-admitted children (29 days to 14 years) with culture-confirmed NTS bloodstream infections were enrolled in a cross-sectional study at Kisantu Hospital, DR Congo. Stool cultures for Salmonella were performed on a subset of enrolled children, as well as on a control group of non-febrile hospital-admitted children. Pairs of blood and stool NTS isolates were assessed for genetic similarity by multiple-locus variable-number of tandem repeats (MLVA) and genomics analysis. Results A total of 299 children with NTS grown from blood cultures (Typhimurium 68.6%, Enteritidis 30.4%, other NTS 1.0%) had a stool sample processed; in 105 (35.1%) of them NTS was detected (Typhimurium 70.5%, Enteritidis 25.7%, other NTS 3.8%). A total of 87/105 (82.9%) pairs of blood and stool NTS isolates were observed (representing 29.1% of the 299 children). Among 1598 controls, the proportion of NTS stool excretion was 2.1% (p < 0.0001). MLVA types among paired isolates were identical in 82/87 (94.3%) pairs (27.4% of the 299 children; 61/66 (92.4%) in Typhimurium and 21/21 (100%) in Enteritidis pairs). Genomics analysis confirmed high genetic similarity within 41/43 (95.3%) pairs, showing a median SNP difference of 1 (range 0–77) and 1 (range 0–4) for Typhimurium and Enteritidis pairs respectively. Typhimurium and Enteritidis isolates belonged to sequence types ST313 lineage II and ST11 respectively. Conclusion Nearly 30% of children with NTS bloodstream infection showed stool excretion of an NTS isolate with high genetic similarity, adding to the evidence of humans as a potential reservoir for NTS.