BACKGROUND: The hydrogeological history of Lake Tanganyika paints a complex image of several colonization and adaptive radiation events. The initial basin was formed around 9-12 million years ago (MYA) from the predecessor of the Malagarasi-Congo River and only 5-6 MYA, its sub-basins fused to produce the clear, deep waters of today. Next to the well-known radiations of cichlid fishes, the lake also harbours a modest clade of only two clupeid species, Stolothrissa tanganicae and Limnothrissa miodon. They are members of Pellonulini, a tribe of clupeid fishes that mostly occur in freshwater and that colonized West and Central-Africa during a period of high sea levels during the Cenozoic. There is no consensus on the phylogenetic relationships between members of Pellonulini and the timing of the colonization of Lake Tanganyika by clupeids. RESULTS: We use short-read next generation sequencing of 10X Chromium libraries to sequence and assemble the full mitochondrial genomes of S. tanganicae and L. miodon. We then use Maximum likelihood and Bayesian inference to place them into the phylogeny of Pellonulini and other clupeiforms, taking advantage of all available full mitochondrial clupeiform genomes. We identify Potamothrissa obtusirostris as the closest living relative of the Tanganyika sardines and confirm paraphyly for Microthrissa. We estimate the divergence of the Tanganyika sardines around 3.64 MYA [95% CI: 0.99, 6.29], and from P. obtusirostris around 10.92 MYA [95% CI: 6.37-15.48]. CONCLUSIONS: These estimates imply that the ancestor of the Tanganyika sardines diverged from a riverine ancestor and entered the proto-lake Tanganyika around the time of its formation from the Malagarasi-Congo River, and diverged into the two extant species at the onset of deep clearwater conditions. Our results prompt a more thorough examination of the relationships within Pellonulini, and the new mitochondrial genomes provide an important resource for the future study of this tribe, e.g. as a reference for species identification, genetic diversity, and macroevolutionary studies.