After his studies, Sullivan clerked for Second Circuit Court of Appeals judge Guido Calabresi and Associate Justice of the Supreme Court of the United StatesStephen Breyer. After the clerkships, Sullivan practiced at Faegre & Benson for several months, and taught law as an adjunct professor at the University of St. Thomas in Minneapolis. After Faegre & Benson, he worked as chief counsel to U.S. Senator from Minnesota Amy Klobuchar, who connected him to Clinton. In 2008, Sullivan was originally an advisor to Hillary Clinton during the primary cycle, and then to Barack Obama during the general election campaign. He prepared Clinton and Obama for debates. When Clinton became U.S. Secretary of State, Sullivan joined as her deputy chief of staff and Director of Policy Planning, and he travelled with her to 112 countries. He became Vice President Biden's top security aide in February 2013 after Clinton stepped down as U.S. Secretary of State. In those posts, he played a role in shaping U.S. foreign policy towards Libya, Syria, and Myanmar. On June 20, 2014, The New York Times reported that Sullivan was leaving the administration in August 2014 to teach at Yale Law School. He is currently a nonresident Senior Fellow at the Carnegie Endowment for International Peace. After his work with the Clinton campaign, Sullivan went on to join the London and New York–based Macro Advisory Partners in January 2017. In this role he spent months representing Uber in its negotiations with labor unions and also assisted companies with forecasting services.
In November 2013, the Associated Press reported that officials in the Obama administration had been in secret contact with Iranian officials throughout 2013 about the feasibility of an agreement over the Iranian nuclear program. The report stated that American officials, including U.S. Deputy Secretary of StateWilliam Burns, Senior White House Iran Advisor Puneet Talwar, and Sullivan, had secretly met with their Iranian counterparts at least five times face-to-face in Oman. Those efforts paved the way for the Geneva interim agreement on the Iranian nuclear program, known officially as the Joint Plan of Action, signed by Iran and the P5+1 countries in Geneva, Switzerland, on November 24, 2013. Since then, Sullivan has regularly attended bilateral consultations with Iran in Geneva as a member of the U.S. delegation on the Iran nuclear negotiations.
Sullivan was the chief foreign policy adviser to Hillary Clinton. He was reported to be the only senior staffer who kept on asking if it wasn’t a good idea for her to spend more time in the Midwestern swing states as the election approached. Sullivan was prominent in many of the Podesta emails released by WikiLeaks during the 2016 US presidential election, including Sullivan questioning if Democratic primary candidate Martin O'Malley's 100% clean energy by 2050 plan was "realistic".