After his dismissal as head coach at FIU, Cristobal was hired by Miami to serve as associate head coach and tight ends coach on January 10, 2013.
Six weeks later, he was hired by Nick Saban to become Alabama's assistant head coach, offensive line coach, and recruiting coordinator.
Cristobal was an elite recruiter at Alabama, finishing No. 1 in the national 247Sports composite rankings in each of his four seasons.
He was named the National Recruiter of the Year by 247Sports in the 2015 cycle and in 2016 he was ranked as the nation's No. 2 recruiter in the country by 247Sports.
Cristobal's Alabama offensive line was awarded as the nation's best in 2015, winning the inaugural Joe Moore Award given to the toughest, most physical line in the nation.
His offensive line ranked in the top 25 nationally in sacks allowed in each of his first two seasons.
Alabama's offensive lines produced standout players and NFL draft picks under Cristobal, including first-team All-American and 2015 first-round draft pick Ryan Kelly and 2014 freshman All-American Cam Robinson, who went on to win the Outland Trophy in Cristobal's final year with Alabama.
In January 2017, Mario Cristobal joined Willie Taggart's staff at Oregon as offensive line coach, with additional duties as co-offensive coordinator (shared with quarterbacks coach Marcus Arroyo) and run game coordinator (along with running backs coach Donte Pimpleton).
On December 5, 2017, he was given the title of interim head coach upon Willie Taggart's departure to Florida State; then, three days later, on Friday, December 8, 2017, Cristobal was officially announced as permanent head coach of the Ducks.
After Taggart's abrupt departure, Cristobal fielded a team in 2018, that would improve to 9-4 and win the Redbox Bowl (formerly the San Francisco Bowl) against Michigan State.
In 2019, Cristobal was voted Pac-12 Coach of the Year by the Associated Press after going 11-2 during the regular season, winning the North division, beating Utah in the Conference Championship, and earning a trip to the Rose Bowl.
That year Cristobal and offensive line coach, Alex Mirabal coached All-American, Penei Sewell who went on to win the Outland Trophy for best interior linemen in the country.
The Oregon offensive line unit was a finalist for the 2019, Joe Moore Award for best overall group in the country. Oregon would finish the post season with a Rose Bowl victory over the Wisconsin Badgers.
In 2020, Cristobal again led Oregon to a Pac-12 Championship, posting a 4–2 record against a conference-only schedule due to the COVID-19 pandemic. Oregon would finish the season with a loss in the Fiesta Bowl to Iowa State.