Rudolph, who entered the game needing 244 yards to pass Brandon Weeden atop the school's passing list, needed less than two quarters to get there. He also threw three touchdown passes and ran for a score for Oklahoma State (2-0).
South Alabama lost starting quarterback Cole Garvin after its first possession and struggled offensively throughout. Garvin, who suffered a lower leg injury, was replaced by Dallas Davis, last year's starter who has been recovering from offseason shoulder surgery.
The uncertainty at quarterback and Oklahoma State's aggressive defense led to the blowout.
South Alabama (0-2) entered the fourth quarter with just six first downs and 92 total yards. The Cowboys forced two second-half turnovers and scored on one to fuel the runaway.
The Jaguars scored with 4:35 remaining when Davis hit receiver Mseiah Francis for a 17-yard scoring pass.
Rudolph fired touchdown passes to receivers James Washington and Marcell Ateman in the first half, then found Ateman again in the third quarter, after a fumble recovery by defensive tackle DeQuinton Osborne set up the Cowboys' offense at the South Alabama 20. Linebacker Justin Phillips returned an interception 25 yards for another Oklahoma State score.
The Cowboys dominated much of the first half, although it didn't completely show on the scoreboard.
Oklahoma State led 20-0 at intermission after outgaining the Jaguars 322-68 in total yards.
South Alabama didn't have a first down until 8:01 remaining in the second quarter, on its fifth possession. At one point, the Jaguars had run 12 offensive plays and the Cowboys had 13 first downs and a 17-0 lead.
On that fifth possession, South Alabama produced its best drive, marching to the Oklahoma State 14, only to have kicker Gavin Patterson miss a 31-yard field goal attempt with 1:17 remaining in the half.
That was more than enough time for the Cowboys to march down the field for a field goal attempt, with kicker Matt Ammendola equaling his career long from 53 yards.
Before that, the Cowboys scored on three straight possessions in the first quarter, starting with a 31-yard field goal by Ammendola.
Touchdowns followed, with Rudolph connecting on scoring passes of 66 yards to Washington and 4 yards to Ateman, boosting the lead to 17-0.
Rudolph was 20-of-29 passing for 276 yards and the two scores in the first half.