Gutiérrez was elected to the Medellín municipal council in the 2003 municipal elections for the New Party and reelected to the same office four years later, but for the Party of the U. In the 2007 election, Gutiérrez received 13,932 preferential votes, which at the time was a local record. In 2008 during his second term he was president of the municipal council. In his first term, Gutiérrez was one of the few councillors who supported then-mayor Sergio Fajardo, and he later supported mayor Alonso Salazar although they later distanced themselves politically. Gutiérrez ran for mayor of Medellín in the 2011 municipal elections, as the candidate of the Party of the U backed by senator Germán Hoyos. He was marginalized in a polarized race between his two main rivals, and placed third with 18.9% of the vote. Gutiérrez's 2011 mayoral aspiration was supported by former PresidentÁlvaro Uribe, although Uribe's preferred candidate, Gabriel Jaime Rico, had failed to win the Party of the U's nomination. Gutiérrez has maintained good relations with Uribism, a redoutable political force in the city and department.
2015 mayoral election
After his defeat, Gutiérrez began planning for a second mayoral candidacy, in the 2015 municipal election. He formalized his candidacy in 2014, forming an alliance with Federico Restrepo with the support of Sergio Fajardo's political movement. Both Gutiérrez and Restrepo did not seek out a political party's nomination, and instead launched their bids independently obtaining ballot access through signatures. His candidacy was challenged by former mayor Alonso Salazar, who had been Fajardo's mayoral candidate in 2007. Salazar entered the race in February 2015 and criticized Gutiérrez for being a "Trojan Horse" for Uribism, because of Gutiérrez's good relations with Uribe's supporters in the city and for supporting Uribe's presidential candidate Óscar Iván Zuluaga in the 2014 presidential election. In June 2015, Restrepo – pressured by Fajardo – dropped his alliance with Gutiérrez and recreated his tandem with Salazar as his ally in the Medellín mayoral race. Nevertheless, Gutiérrez remained strong in the polls, although trailing Juan Carlos Vélez, the candidate of Uribe's Democratic Center by the end. Two weeks before the election, the Liberal Party's candidate Eugenio Prieto dropped out and endorsed Gutiérrez, in an effort to unite forces against Juan Carlos Vélez. Gutiérrez was the surprise winner of the mayoral election on October 25, 2015, defeating Juan Carlos Vélez by 9,589 votes to 236,632 votes ). As Mayor a figure in the top positions of the National Ranking of Mayors, with Alejandro Char, Juan Pablo Gallo and Rodolfo Hernández Suárez and Marcos Daniel Pineda.
