Here, we present 12 loci paternal haplotypes (Y-STR profiles) against the backdrop of the Y-SNP marker system of Bantu males from the Maputo Province of Southeast Africa, a region believed to represent the southeastern fringe of the Bantu expansion. Our Maputo Bantu group was analyzed within the context of 27 geographically relevant reference populations in order to ascertain its genetic relationship to other Bantu and non Bantu (Pygmy, Khoisan and Nilotic) sub-equatorial tribes from West and East Africa. This study entails statistical pair wise comparisons and multidimensional scaling based on YSTR Rst distances, network analyses of Bantu (B2a-M150) and Pygmy (B2b-M112) lineages as well as an assessment of Y-SNP distribution patterns. Several notable findings include the following: 1) the Maputo Province Bantu exhibits a relatively close paternal affinity with both east and west Bantu tribes due to high proportion of Bantu Y chromosomal markers, 2) only traces of Khoisan (1.3%) and Pygmy (1.3%) markers persist in the Maputo Province Bantu gene pool, 3) the occurrence of R1a1a-M17/M198, a member of the Eurasian R1a-M420 branch in the population of the Maputo Province, may represent back migration events and/or recent admixture events, 4) the shared presence of E1b1b1-M35 in all Tanzanian tribes examined, including Bantu and non-Bantu groups, in conjunction with its nearly complete absence in the West African populations indicate that, in addition to a shared linguistic, cultural and genetic heritage, geography (e.g., east vs. west) may have impacted the paternal landscape of sub-Saharan Africa, 5) the admixture and assimilation processes of Bantu elements were both highly complex and region-specific.