In 2003, he was hired by Steve Kragthorpe as the defensive coordinator at Tulsa, where he helped guide the Golden Hurricane to two bowl games in three seasons.

Graham built one of the best defensive units in Conference USA and the nation before leaving the position following his third year at Tulsa for his first head coaching stint.

[3] Graham was named Conference USA Coach of the Year, and was rewarded by the Rice administration with the offer of a significant pay raise and contract extension.

With an annual salary of $1.1 million Graham was the second-highest-paid coach in Conference USA, behind SMU's June Jones in 2010.

In his final season at Tulsa, the team reached a 10–3 record that included a 28–27 upset at Notre Dame and 62–35 win over No.

[12][13] He was hired after Michael Haywood, the initial choice to replace sixth-year coach Dave Wannstedt, was fired after a domestic dispute.

Less than one year from his hiring, on December 13, Graham informed athletic director Steve Pederson that he had discussed a head coaching opportunity at Arizona State.

[15] Graham informed the Pitt players of his departure the following day by having a text message forwarded to the team by director of football operations Blair Philbrick.

[16] Two weeks prior to leaving Pitt, Graham referred to assistant coaches who left to join the staff of Rich Rodriguez at Arizona as "nothing but mercenaries.

With a win in the Kraft Fight Hunger Bowl against the Navy Midshipmen, the 2012 Sun Devils won the final three games of the season for the first time since 1978.

[26] ESPN's Pac-12 Blog writer Ted Miller called Graham's first season at Arizona State an "unquestioned success.

"[27] In 2013, Graham continued to build positive momentum and led ASU to win the Pac-12 South after defeating UCLA and rival University of Arizona.

[29] The 2015 season saw a big drop off for the program as the Sun Devils finished a disappointing 6–7 with a 43–42 loss to the West Virginia Mountaineers in the Cactus Bowl.

Nevertheless, Graham's team slowly gelled together after a slow start, notably pulling off a huge upset over previously undefeated Nevada.

"[31] This led to numerous Hawaii players entering the transfer portal, including his son, Michael Graham.

[33] The meeting included a group of players and family testifying, with numerous accounts criticizing Graham and his conduct.

The allegations included such enormities as him saying those playing the ukulele were "fucking annoying", describing players as "porch monkeys" and "pineapple pickers", and calling Hawaii a "third world country" for not having Dr Pepper in the vending machines.

[34][35] Graham resigned from Hawaii on January 14, 2022, having completed his second year of a five-year contract and an 11–11 record amidst controversy of mistreatment of players.