Gray would take over half-way through his rookie year as New England's starting Left Tackle, and along with John Hannah, they would become one of the best Tackle/Guards tandem and the building block of a rising Patriots Team.  Gray went to the Pro Bowl in 1976 and again in 1978.  He likely would have gone to one in 1977, but both he and Hannah held out looking for a better contact, and they missed three games.

Gray was also a First Team All-Pro in 1978, but that would be his last year with the team, as he was traded to the Houston Oilers in what appeared to be a cost-cutting move.  The transaction was hated by fans and teammates alike, as Hannah stated: "there goes the Super Bowl" upon learning of the news.

Gray started all but one of his games as a Patriot, and he went into the Patriots Hall of Fame in 2019.