On April 27, 1962, he was traded to the Dallas Cowboys in a three-team deal, with the Green Bay Packers acquiring kicking specialist Allen Green and the Giants obtaining a draft pick from the Packers. He reunited with former teammate Tom Landry, who used Nolan as a "player-coach". When Nolan was injured halfway through his first season, he became the Cowboys' defensive coordinator.
Nolan was on the Cowboys' staff for six years, the last year being the season in which the Cowboys played in the Ice Bowl. Afterwards, he was head coach of the San Francisco 49ers for eight seasons from 1968 through 1975, noted for developing the defense and taking the team to three straight NFC West division titles (1970–72), twice missing the Super Bowl by only one game (1970–71). Additionally, he was head coach for the New Orleans Saints from 1978–80 going 15–29. He was the first Saints head coach to win six, seven, and eight games in a single season, going 7–9 in 1978 and 8–8 in 1979. Nolan was fired by the Saints in 1980 after an 0–12 start. His last game was on November 24 of that season, a 27–7 loss to the Los Angeles Rams on Monday Night Football. The Saints finished the 1980 season 1–15, as interim coach Dick Stanfel won only one of his four games, a 21–20 victory over the New York Jets in week 15.
Nolan was well known for wearing business suits while coaching, as did many other coaches during his era. The league has since disallowed this practice in most circumstances due to the league signing exclusive apparel deals with sportswear companies (specifically Reebok). The league made an exception after Nolan's death in 2007, allowing Nolan's son Mike and Jack Del Rio, coach of the Jacksonville Jaguars, to wear suits in the elder Nolan's honor.