Kelly was the mayor of Saint Paul, Minnesota from in 2001. He won the office in 2001 by just 403 votes in a tight race with Jay Benanav, a city councilman. As mayor, he was noted for his efforts to increase the minimum wage and create and retain high-paying jobs.

During Kelly's term in office, his political views and several appointments generated controversy. In 2004, he rankled fellow Democrats by endorsing and campaigning for President George W. Bush's re-election. According to critics, his conservative views, which may have been intended to garner support from Republicans and independents, undermined his constituent base in the Democratic Party. An unsuccessful grassroots campaign to recall him was launched shortly after his announcement in support of Bush's re-election effort.

In 2005, one of Kelly's appointees, Sia Lo, head of the criminal division of the city attorney's office, was reported to be at the center of an investigation into alleged corruption in a city development deal which focused on a new Hmong funeral home on the city's West Side. Lo was never charged.

The top two getters advanced to the November 8th general election.