Sullivan began his Secret Service career as a special agent assigned to the Detroit Field Office in 1983 after having served for five years as a special agent in the Office of the Inspector General for the U.S. Department of Housing and Urban Development. In 1990, Sullivan began working at the Fraud Division in Washington, D.C. One year later, in 1991, Sullivan was assigned to the Presidential Protective Division. In 1996, he was made Assistant Special Agent in Charge of the Office of Protective Operations. From 1997 to 1998 he was the resident agent in charge of the Columbus, Ohio, office. After being special agent in charge of the Counterfeit Division from 1998 to 1999, he returned to the Presidential Protective Division in 1999. In July 2000, Sullivan was made a Deputy Assistant Director in the Office of Protective Operations. In 2002, he was reassigned to the position of Deputy Special Agent in Charge of the Vice Presidential Protective Division. A year later, he was reassigned to the position of Deputy Assistant Director, Office of Human Resources and Training. In 2006, Sullivan was appointed by George W. Bush to the position of Director of the Secret Service. On February 1, 2013, Sullivan announced he was retiring after 30 years with the agency to be effective February 23. After his retirement, Sullivan partnered with Noah Kroloff, Dennis Burke, David Aguilar, John Kaites and Jerry Reinsdorf to found .
In April 2012, a scandal involving the President's security detail received international press attention. The scandal involved 11 agents and more military personnel from all four branches who allegedly engaged prostitutes while assigned to protect President Barack Obama at the 6th Summit of the Americas in Cartagena, Colombia. As of April 24, nine employees had resigned or retired. Starting June 30, 2011, agents on the Presidential Protection Detail were ordered to leave their posts and conduct surveillance on a neighbor of Lisa Chopey, Sullivan's assistant, in an operation named "Moonlighting". This continued for at least several days and according to some accounts, months. The neighbors eventually moved away, they said partly because of the intimidation.