Valencia began his career playing for the youth ranks of America de Cali, eventually being promoted to the first team in 2003. After three years at the club, Valencia was transferred to Brazilian side Atlético Paranaense along with fellow countryman Julián Viáfara. There, Valencia would turn into an important factor for Paranaense, making it into the club's starting lineup. After an impressive conquest of the Campeonato Paranaense in 2009, Valencia sparked the interest of league giants, Fluminense. In 2010, he officially signed for the Flu. Although not being a regular starter, Valencia has won important titles since being at Fluminense. Due the injury of the starting defensive midfielder, Diogo, Valencia became his replacement for the 2010 season. Fluminense eventually crowned themselves league champions in 2010, with Valencia being a fundamental part.