Fedora played wide receiver at Austin College before starting his coaching career as a graduate assistant there in 1986.

He spent four seasons as head coach of the junior varsity team at Garland High School, which at the time was a powerhouse in Texas high school football, but then returned to the collegiate ranks, coaching tight ends, wide receivers and running backs for six seasons (1991–96) at Baylor.

In November 2007, Fedora was rumored to be a candidate for the head coaching job at Baylor University, which eventually went to Art Briles.

[6] He made a big splash in his first recruiting season, as Fedora was able to land five-star prospect DeAndre Brown, who had offers from several Southeastern Conference schools, such as LSU, Ole Miss, and Auburn.

Fedora opened his first season as head coach at Southern Miss with a 51–21 drubbing of Louisiana–Lafayette, in which the Golden Eagles broke the school record for total yards in a single game with 633.

[7] In 2011, Fedora led his 24th-ranked Southern Mississippi team to winning the Conference USA championship by defeating Kevin Sumlin's then-No.

[8] On December 7, 2011, ESPN's Joe Schad reported that Fedora accepted an offer to take the job at North Carolina, but still planned to coach the Golden Eagles in the 2011 Hawai'i Bowl.

"[12] Fedora was already a familiar face to recently hired UNC athletic director Bubba Cunningham, who had arrived a few months earlier from Conference USA rival Tulsa.

Fedora knew that he would not be able to compete in post-season play in his first year due to NCAA probation for recruiting and academic violations.

[15] According to WNCN in Goldsboro, Fedora spoke with former Baylor coach Chuck Reedy, who'd given him his first full-time collegiate job, and said that he "turned down more money than I ever thought I'd see" because he was more than happy in Chapel Hill.

Partly to address this, Fedora hired former Auburn head coach Gene Chizik as defensive coordinator for the 2015 season.

They then defeated Virginia Tech in overtime 30–27 to clinch their first official Coastal Division championship, as well as the eighth 10-win season in school history.

Unable to duplicate his team's success from a season earlier, the Tar Heels lost in the Sun Bowl to Stanford with a score of 25–23.

And I do believe that if it gets to that point, our country goes down, too.” He then relayed a story where he purportedly asked a three-star general what makes America's military the "greatest" on earth.