After his playing career ended, Johnson began working as an assistant coach for the New England Patriots. In New England he was reunited with Bill Belichick, for whom Johnson played as a Giant and Brown. He spent 14 seasons with the organization, winning three Super Bowls, before leaving the Patriots to work as the defensive line coach for the Buffalo Bills and then the Jets.
Johnson was drafted by the New York Giants in the second round of the 1986 NFL Draft. With the Giants, he was a member of both the Super Bowl XXI and Super Bowl XXV-winning teams, under head coach Bill Parcells and assistant Bill Belichick. After seven seasons in New York, Johnson re-joined Belichick with the Cleveland Browns in 1993, Belichick's third season as the team's head coach. After the 1995 season, the Browns moved to Baltimore, Maryland, and neither Belichick nor Johnson followed the team there. Johnson instead joined the Detroit Lions, whom he spent one season with in 1996. For what would become the final two seasons of his career, Johnson again re-joined Belichick, who was then serving as the defensive coordinator for the New York Jets under Parcells. After the 1998 season, Johnson retired from the NFL with career totals of 25.5 sacks, 12 forced fumbles, 14 interceptions, and over 1,200 tackles.
Johnson began his coaching career as an assistant linebackers coach with the Patriots during the 2000 season. Johnson then served as the Patriots' inside linebackers coach from 2001 through 2003, before moving to defensive line coach in 2004. In 2012, he returned to linebackers coach.
With Bill Gutman, Johnson wrote Won For All, an account of the Patriots 2001 championship season, which was published by Contemporary Books, a McGraw-Hill company, ISBN 0-07-140877-0.
On January 21, 2014, Johnson announced he would be leaving the Patriots. On January 31, 2014, the Buffalo Bills announced Johnson as their new defensive line coach, replacing Anthony Weaver, who left for a similar position in Cleveland.