Tréllez was born in Turbo, Antioquia, and started playing for Atlético Nacional in 1985. He scored his first goal as professional the same day the debuted against Cúcuta Deportivo. With Atlético Nacional Tréllez scored a total of 116 goals, 14 of which were against Independiente Medellín, Atlético Nacional's eternal rivals. In 1992, he became the top goal scorer in Colombia with 25 goals, becoming the first Colombian to become the league's goal scorer for Atlético Nacional. In 1994, Tréllez became the first Colombian to ever play for Boca Juniors of Argentina, where he scored two goals in 19 games, in all competitions.
At the international level, Tréllez also played two seasons for FC Zürich and then played in the United States for the Dallas Burn.