Prochilodus magdalenae is a freshwater fish endemic to the Colombian Magdalena-Cauca and Caribbean hydrographic basins. The genetic structure patterns of populations of different members of Prochilodus and the historic restocking of its depleted natural populations suggest that P. magdalenae exhibits genetic stocks that coexist and co-migrate throughout the rivers Magdalena, Cauca, Cesar, Sinú and Atrato. To test this hypothesis and explore the levels of genetic diversity and population demography of 725 samples of P. magdalenae from the studied rivers, we developed a set of 11 species-specific microsatellite loci using next-generation sequencing, bioinformatics, and experimental tests of the levels of diversity of the microsatellite loci. The results evidenced that P. magdalenae exhibits high genetic diversity, significant inbreeding coefficient ranging from 0.162 to 0.202, and signs of erosion of the genetic pool. Additionally, the population genetic structure constitutes a mixture of genetic stocks heterogeneously distributed along the studied rivers, and moreover, a highly divergent genetic stock was detected in Chucurí, Puerto Berrío and Palagua that may result from restocking practices. This study provides molecular tools and a wide framework regarding the genetic diversity and structure of P. magdalenae, which is crucial to complement its baseline information, diagnosis and monitoring of populations, and to support the implementation of adequate regulation, management, and conservation policies.