Valencia begon zijn carrière bij de jeugdopleiding van América de Cali. In 2003 kwam hij terecht bij het eerste elftal. Na drie jaar gespeeld te hebben voor América de Cali kreeg Valencia een transfer naar Clube Atlético Paranaense, samen met zijn landgenoot Julián Viáfara. Na een aantal seizoenen te hebben gespeeld in de Campeonato Paranaense, maakte Valencia in 2010 een transfer naar Fluminense.
Valencia maakte deel uit van de Colombiaanse selectie die in 2005 deelnam aan het WK voetbal U20 in Nederland. Daar verloor de ploeg van bondscoach Eduardo Lara in de achtste finales van de latere kampioen Argentinië (2-1).