Britt and Mathis opened huge hole after huge hole on the left and right sides of the line, and tons of rushing yards and scores followed.
And Connelly faces a huge challenge - rebuilding the line they left behind, a task which has been made even tougher by the line's recent injury struggles.
Look around Crimson Tide preseason camp, and you see plenty of experience.
The offense is slightly younger and more frail, but its skill players are clearly a step ahead of where they were a year ago.
Quarterback Brodie Croyle, tailback Kenneth Darby and fullback Tim Castille appear all but recovered from major offseason surgeries, with Castille the laggard of the three (only by a little) because his right knee reconstruction was so arduous.
That leaves one problem - the offensive line.
Unless things change dramatically, it appears the line will make - or break - the Alabama offense this season. And to avoid breaking it, the line must become something less than broken-down itself.
With two weeks remaining before the season opener with Middle Tennessee State, this is where the line stands: Its left tackle, sophomore Chris Capps, has never started a college football game, but has faced little competition in preseason camp because his backup, redshirt freshman Cody Davis, has battled a hamstring strain.
Left guard Antoine Caldwell earned his starting spot in spring and was coming along just fine until a sprained right ankle forced him out of action for a week.
Now senior Taylor Britt is manning the position until Caldwell returns.
Center J.B. Closner is a high point, the line's clear leader. But how many good things can you say about a guy who is a two-year starter, yet was rumored to be moving to left guard to clear the way for Caldwell this spring?
Right tackle Kyle Tatum should be just fine; he's developing into a solid bookend tackle who is learning more about the offensive line every day.
But right guard is a mess, pure and simple. In a perfect world, fifth-year senior Mark Sanders, a program veteran who knows all four tackle and guard positions, would have claimed the spot as his own by now. But Sanders has struggled just enough to open the door for competition, and competition has come barreling through.
Redshirt freshman B.J. Stabler was making a strong push until he hurt a knee in Monday's scrimmage. He'll be out at least three to four weeks following Wednesday's arthroscopic surgery to repair a slight cartilage tear.
That brought true freshman Marlon Davis into the mix. By all accounts, Davis is a solid prospect - a Georgia Class 4A All-state pick who had 87 pancake blocks and graded out at 92 percent his senior season.
But putting a true freshman into your offensive line mix is dangerous at best; Alabama hasn't had a true frosh start since Dante Ellington turned the trick in 1999, and you know how that turned out. Lost his job to some freshman named Mathis, if memory serves.
Davis has the potential to be a good offensive lineman, eventually.
But if he has to play this season, he'll be either the steal of the Class of 2005 or in way, way over his head. It's Connelly's job to turn this jumbled mess into something resembling a productive, protective offensive line.
Right now, it can run-block, but pass-blocking is an adventure.
Considering Croyle's fragile health history, that's bad news.
If Alabama is to achieve the lofty expectations fans have (and it has for itself), Croyle is the linchpin, and he must stay healthy.
He'll have much better luck doing that if he isn't dodging defensive ends and linebackers looking for a SportsCenter moment like Georgia's Odell Thurman got two years ago when he rammed Croyle into the Sanford Stadium turf.
Croyle makes the offense go. He knows the young receiving corps, and he takes pressure off the backfield, allowing the offense to hum in three-part harmony.
But he can't do any of that if he's watching from the sideline on crutches or with his throwing arm in a sling. He has to rely on the offensive line, as do the rest of his teammates.
Right now, that isn't easy to do.
Greg Wallace is the Alabama beat writer for the Birmingham Post-Herald. He writes a weekly column for BamaMag.com.