Haynes went to T.S. King Middle School, as stated by him in the 2012 recognition for his Hall of Fame (NFL) awards. Haynes played cornerback at John Marshall High School in Los Angeles. The team on which he played chose two all star players to represent Marshall, which would eventually lead to his further career. In addition to football, Haynes also participated in track and field and currently holds the long jump record at John Marshall High School. During his Senior Year (1971) Haynes started both ways on offense (QB) and defense (Cornerback). However, Marshall went 0-7-1 in the Northern League in 1971 and tied Belmont 20-20 in his final game. In a show of his athletic accomplishments, John Marshall High School named the school football stadium in his honor when he was inducted into the school football hall of fame in 1986.
In his final regular season track meet, Haynes had to run the final leg of the Mile Relay, then rest before completing his final long jump effort. The opposing team (arch rival Belmont), believing they had won the league championship, loaded their bus and went home. Haynes rested, then leaped 23'5", a school record that still stands, winning the event, the meet and the league championship with it.
Haynes was selected in the first round in the 1976 NFL Draft by the New England Patriots. He enjoyed a sensational rookie year with the Patriots with eight interceptions and an AFC-leading 608 yards on 45 punt returns. That year, Haynes gave the Patriots their first-ever touchdowns on punt returns with 89-yard and 62-yard returns. He earned a Pro Bowl invitation as a rookie, the first of nine Pro Bowl bids. He also won NFL Defensive Rookie of the Year honors. The 1976 Patriots had an 11-3 record and clinched a playoff berth for the first time in 13 years. In the first round the Patriots lost to Oakland Raiders 24-21. In 1978 Haynes had 6 interceptions and returned one of them for a touchdown against the Baltimore Colts. The Patriots won their division but lost to the Houston Oilers in the playoffs. Haynes played 4 more seasons with New England with 9 picks and a single touchdown in 1980 against the rival New York Jets.
Haynes recorded 28 interceptions and 1,159 yards on 111 returns, a 10.4-yard average during his seven years with the Patriots. He started his career with 58 consecutive starts before being sidelined with a rib injury late in 1979. Haynes was inducted into the Patriots Hall of Fame in 1994 and number was retired as well.
Haynes played out his option with the Patriots in 1982, and in November, 1983, his contract was awarded to the Los Angeles Raiders in a settlement that gave the Patriots a No. 1 draft choice in 1984 and a No. 2 pick in 1985. After playing the last five regular season games, he started in the Raiders’ Super Bowl XVIII victory, notching one interception, two pass breakups and one tackle. His partner in the Raiders' secondary was Lester Hayes, and the tandem was quickly recognized as one of the best cornerback duos in league history. Washington Redskins general manager Bobby Beathard later said that Haynes tipped the balance heavily in the Raiders' favor. The Raiders and Redskins had played in the regular season when Haynes was still a Patriot, and his addition gave the Raiders the luxury of having two shutdown corners.
In seven seasons with the Raiders, Haynes returned only one punt but he added 18 interceptions to give him a career total of 46 which were returned for 688 yards and two touchdowns, including a team-record 97-yard return against Miami in 1984. Haynes was an All-Pro choice in 1977, 1978, 1982, 1984 and 1985 and an All-AFC pick eight times.
In 1997, he was elected to the Pro Football Hall of Fame. In 1999, he was ranked number 93 on The Sporting News' list of the 100 Greatest Football Players. Haynes is considered by many football experts to be the best overall cornerback in the history of the NFL.
In the video game All Pro Football 2K8, Haynes originally appeared as a Gold Cornerback with the abilities "Coverage Bonus - Player has excellent pass coverage skills" and "Return Specialist - Player is skilled at returning punts or kicks". After the first patch for the XBox 360 version of the game however, Haynes' name was changed to "Mark Smith". No explanation for the change was ever presented. All of Mark Smith's abilities, player model, and even facial features, remained unchanged from those of Haynes.