The valley of the Magdalena River is one of the main population pathways in Colombia. The gene pool and spatial configuration of human groups in this territory have been outlined throughout three historical stages: the Native pre-Hispanic world, Spanish colonization, and XIX century migrations. This research was designed with the goal of characterizing the diversity and distribution pattern of Y-chromosome lineages that are currently present in the Tolima and Huila departments (middle Magdalena River region). Historic cartography was used to identify the main geographic sites where the paternal lineages belonging to this area have gathered. Twelve municipalities were chosen, and a survey that included genealogical information was administered. Samples collected from 83 male volunteers were analyzed for 48 Y-SNPs and 17 Y-STRs. The results showed a highly diverse region characterized by the presence of 16 sublineages within the major clades R, Q, J, G, T and E and revealed that 93% (n = 77) of haplotypes were different. Among these haplogroups, European-specific R1b-M269 lineages were the most representative (57.83%), with six different subhaplogroups and 43 unique haplotypes. Native American paternal ancestry was also detected based on the presence of the Q1a2-M3*(xM19, M194, M199) and Q1a2-M346*(xM3) lineages. Interestingly, all Q1a2-M346*(xM3) samples (n = 7, with five different haplotypes) carried allele six at the DYS391 locus. This allele has a worldwide frequency of 0.169% and was recently associated with a new Native subhaplogroup. An in-depth phylogenetic analysis of these samples suggests the Tolima and Huila region to be the principal area in all Central and South America where this particular Native lineage is found. This lineage has been present in the region for at least 1,809 (+/- 0,5345) years.