In 1994, Johnson assumed the role of executive director of the Democratic Study Group, a legislative service organization in the House of Representatives. The following year, he became an assistant secretary on the staff of South Dakota Senator Tom Daschle. In 1996, Daschle named Johnson the staff director of the Senate Democratic Leadership Committee, specializing in policy and communications strategy. During Johnson's five-year tenure with Daschle, the "Pittsburgh Post-Gazette" reported that he was a key strategist behind the Democrats' efforts to positively frame their role in the 1995 government shutdown, and he worked on the Democratic Policy Committee as the staff director of leadership communications. He also oversaw the running of the Democratic Senate leadership's television studio, completed in 1996, in the Hart Senate Office Building.