Pareja came up through the youth system of Atlético Nacional; however, he began his professional career in 1987, debuting for renowned club Independiente Medellín, and assisted on the winning goal in a 1-0 victory on his debut. He played eight years with Independiente Medellín, from 1987 to 1995, helping them to be runners-up in 1993, and leading them to a respectable performance in the 1994 Copa Libertadores. In 1995, Deportivo Cali purchased Pareja from Independiente Medellín; Pareja paid immediate dividends, helping Cali to a championship in the 1995-1996 season, their first in 22 years. He would stay with them four years, before signing with Major League Soccer of the United States.
He was allocated to New England Revolution on 26 May 1998, but was soon traded to Dallas Burn for Mexican forward Damian Alvarez. This proved to be one of several poor trades that the Revolution would make at this time, as Pareja would go on to become a fixture in Dallas' midfield for years to come, and Damian would only play two games with the Revs before leaving the league. Although Pareja played little for Dallas in 1998, he earned himself a place at the center of Dallas's midfield for the 1999 season, playing 27 games and scoring four goals and six assists, while coordinating the Burn attack. Pareja remained in this position for eight years, playing in 189 regular season games for Dallas, while scoring 13 goals and 52 assists, and was named to the MLS Best XI in 2002. Pareja announced he would retire following the 2005 MLS season and took a job as an assistant coach with FC Dallas.
On 5 January 2012, Colorado Rapids signed Pareja as head coach. He stepped down on 4 January 2014. On 10 January 2014 Pareja was announced as the head coach of his former club, FC Dallas, after Dallas traded a first-round 2015 MLS SuperDraft pick and allocation money to Colorado.