In the mid-1990s, he was the executive director of the Arctic Winter Games, which were held in 1996 in the northern Anchorage communities of Chugiak and Eagle River.

In 2005, he voted against an Anchorage Water and Wastewater Utility rate increase and in 2006 he challenged a city ordinance limiting the size and style of signs.

Sullivan campaigned on a platform of reducing city spending and crime, and confronting what he termed "an energy crisis" as the result of dwindling natural gas reserves in Cook Inlet.

Mayor Sullivan gained nationwide attention for vetoing Assembly legislation which would have included municipal protections against discrimination based on sexual orientation.

[3] Additionally, he passed an ordinance that banned sitting on public sidewalks at certain times and vetoed an attempt by the assembly to repeal it.

[4][5][6] Sullivan was re-elected to a second three-year term in April 2012, defeating Assemblyman and former Anchorage Police Department spokesman Paul Honeman.

On June 1, 2016, Sullivan announced he would be a candidate in the Republican primary for the U.S. Senate seat currently held by Lisa Murkowski.