Marcus Lattimore rushed for a career-high 247 21.
Lattimore controlled the clock and the Navy defense with 37 carries and caught four passes for 25 yards.
Stephen Garcia went 18-of-25 for 204 yards and an interception for the Gamecocks (3-0), who play Vanderbilt next Saturday.
Alexander Teich ran for 93 yards and a score and quarterback Kriss Proctor carried the ball 17 times for 72 yards and a touchdown. John Howell also had a rushing touchdown out of Navy's triple option attack, which was upstaged by the bullish Lattimore.
The Midshipmen (2-1) next play on October 1, versus Air Force.
Navy's triple option found its stride on the team's second possession, as runs of 30 and 27 yards by Gee Gee Greene and Howell, respectively, book-ended a 65-yard touchdown drive.
South Carolina evened the score behind it's singular bruiser -- Lattimore, who capped a seven-play drive with five consecutive runs, the last of which found paydirt from six yards out. It marked the first touchdown Navy has allowed in the first quarter this season.
The Midshipmen responded with a methodical, 77-yard drive, burning nearly six minutes of clock before taking a 14-7 lead on Proctor's five-yard touchdown plunge.
"That clock keeps running when you play a team like Navy," said Gamecocks head coach Steve Spurrier. "That's how Navy beats a lot of teams."
On their next possession, a 34-yard strike from Garcia to Nick Jones moved the chains on 3rd-and-15. Lattimore then reeled off runs of six, 16 and five yards -- the last of which resulted in a game-tying score.
The half drew to a close with a pair of critical fourth down plays. The Midshipmen were denied on 4th-and-2 when Devin Taylor stuffed Proctor on a keeper up the middle. Minutes later, Garcia converted a 4th-and-10 to Justice Cunningham, who scampered out of bounds at the Navy 37. A short pass to Lattimore set up a 48-yard field goal from Jay Wooten in the waning seconds of the first half.
South Carolina was poised to add to its lead on the third quarter's opening drive, but Garcia was intercepted by Kwesi Mitchell at Navy's 11-yard line.
The Midshipmen capitalized with an 86-yard touchdown drive to grab a 21-17 advantage.
During the go-ahead march, Proctor converted a 3rd-and-10 from his won 20 with a 33-yard completion to Bo Snelson. Later in the drive, Teich fumbled after a 21-yard scamper, but Howell recovered the ball at South Carolina's 10-yard- line to prolong the possession. Teich's two-yard rushing touchdown finished the drive.
Again the Gamecocks turned to Lattimore. He touched the ball 11 times on a 15- play, 80-yard drive. After Garcia converted a 4th-and-1 with his legs, Lattimore barreled seven yards into the end zone to give the Gamecocks a 24-21 lead.
"When it comes to the fourth quarter, as I get more carries, I get stronger," said Lattimore.
The Midshipmen then went three-and-out, but were given another chance after Lattimore was stuffed on a 4th-and-1 at the Navy five-yard line.
With 3:03 remaining a false start penalty forced Navy into a 4th-and-14 from its own 13-yard line. Proctor kept hope alive, however, with a 15-yard completion to a leaping Matt Aiken.
The drive failed, though, as Antonio Allen intercepted Proctor four plays later to seal the South Carolina victory.
"It's just a play you wish you had back," said Proctor. "The safety was coming down in the final play and I just didn't make a good throw."
Lattimore's 246 rushing yards were the most-ever by a player on an NCAA team coached by Steve Spurrier...Spurrier is 43-0 against non-BCS schools...the Gamecocks lead the all-time series 5-3...It was the programs' first meeting since 1988.