The Neotropical genus Pseudopimelodus (Siluriformes, Pseudopimelodidae) is the second most widely distributed genus in South America comprising four valid species that inhabit different trans- and cis-Andean rivers. Of the two species recorded in Colombia, P. schultzi is distributed in the Magdalena-Cauca and Caribbean basin and P. bufonius is distributed in the Atrato River basin and Orinoco-Amazon river basins. Several paleogeographic processes resulting from Andean orogeny in northwestern South America may promote genetic diversification in the genus Pseudopimelodus in Colombia. To test this hypothesis, we conducted phylogenetic analyses based on Bayesian Inference by using a partial sequence of the Nuclear Recombination-Activating gen (rag2) and the subunit 1 Cytochrome C Oxidase gene (COI). Furthermore, two new Pseudopimelodus species from the Magdalena-Cauca River Basin were described here based on osteological and morphometric characters: Pseudopimelodus sp. nov. 1 from Cauca River upper and middle sectors and Magdalena River upper sectors and Pseudopimelodus sp. nov. 2 from Cauca River lower sector and Magdalena River middle and lower sectors. In addition, a set of 13 microsatellites were developed by using next generation sequence technology to assess the genetic diversity and genetic structure of these two new Pseudopimelodus species. Results of Bayesian phylogenetic analyses releaved that the genus Pseudopimelodus in Colombia comprises at least five different, well-delimited evolutionary lineages, the divergence times of which agree with the geological history of northwestern South America. Moreover, microsatellite analyses showed that both new species exhibited high levels of gene flow among sample sites, and high genetic diversity compared to the mean levels of genetic diversity reported for Neotropical Siluriformes. The results obtained in this study are crucial for designing local and regional management strategies for Pseudopimelodus fisheries in Colombia.