In 2009 Garzón joined forces with former Mayors Enrique Peñalosa and Antanas Mockus to re-found the Green Party, an eco-oriented political movement.

Considered by some analysts as an idiosyncratic and charismatic speaker, "Lucho" Garzón has been one of the most visible critics of President Álvaro Uribe's government, running against him on a shoe-string budget in the 2002 presidential race and finally making third place with 680,245 votes (6.16% of the voter turnout).

Garzón defeated Juan Lozano, the candidate favored by president Uribe and also by influential media groups as El Tiempo in Bogotá, in the mayoral elections in October 2003.

Garzón's low budget campaign received a major boost when his candidacy was endorsed by the more leftwing sectors of the Liberal party, in particular those close to then senator Piedad Córdoba.

During his tenure as mayor, Garzón was popular amongst the people of Bogotá as reflected in polls, in spite of confronting such difficult issues as the use of public space, the teething problems faced by the TransMilenio mass-transport system, and how to deal with ex-combatants from Colombia's armed conflict who had been settled in Bogotá as part of a central government rehabilitation program (eventually, Garzón and Uribe jointly decided to change some aspects of the program, after a bomb exploded near one of the shelters for former irregular fighters).