Oklahoma State (17-14) led 73-63 with 1:02 to play on Adrian Peterson's two free throws and seemingly had the game in hand.
But Keith Harris hit a 3-pointer and, after two Oklahoma State free throws, Chris Cameron followed with another trey. After a 20-second time out, Cameron hit a 3-pointer to pull Tulane within 75-72 with 39.5 second to go.
Adrian Peterson then hit one of two free throws and Adkins followed with two more to give Oklahoma State a 78-72 lead with 27.3 seconds left.
Peterson, who scored 19 points for the game, added one more free throw with 20.1 seconds left to close out the scoring.
Oklahoma State took a 38-25 halftime lead after starting slow.
Chianti Roberts hit a short jumper at the 15:23 mark to give the Cowboys a 6-5 lead and Oklahoma State never trailed again. He finished with nine points.
Marlon Dorsey, who scored 13 points, hit the first of three 3-pointers at the 13:20 mark to give the Cowboys a 13-10 lead.
Dorsey, who was three of five from 3-point range, hit another with 10:32 to play in the half and added a third to give Oklahoma State a 27-18 lead.
Jerald Honeycutt led Tulane (20-11) with 17 points, but was 4-of-17 from 3-point range. Cameron added 15 points for Tulane while Dylan Osean and Lawrence Nelson each had 10.
The Cowboys drew Michigan as their second-round matchup. The game will be played Tuesday at 7:30 p.m. in Crisler Arena.
The Wolverines won the last time the two teams met, 75-72 in the 1992 NCAA Southesat Regional.