Fryatt bagged the first from the penalty spot and then headed home a second to spark celebrations from the 2,141 travelling fans.
Southend created the two best chances of a first half notable for a lack of goalmouth action.
The first came after 40 minutes when striker Theo Robinson went closest to breaking the deadlock.
His low 20-yard effort was turned round the right post for a corner by a diving David Stockdale.
The Blues followed it up four minutes later when a Simon Francis free-kick from the right was flicked on by Lee Barnard to Peter Clarke at the back post, but he could only half-volley over the bar from eight yards.
Leicester's best opening came after six minutes when Max-Alain Gradel teed up Lloyd Dyer but the winger saw his shot blocked by Clarke.
Southend picked up from where they left off after half-time with Barnard's flick finding Robinson, who blasted the ball against the crossbar in the 48th minute.
Two minutes later the woodwork came to the Shrimpers' rescue after Foxes striker Matty Fryatt burst into the centre of the box, rounded goalkeeper Steve Mildenhall but saw his shot hit the right post from an acute angle.
Southend manager Steve Tilson replaced central midfielder Jean-Francois Christophe with Anthony Grant, but he only lasted three minutes before being stretchered off the pitch following an aerial clash with City skipper Matt Oakley.
But it was Leicester who broke the deadlock in the 60th minute when referee Clive Penton awarded a penalty for handball against Francis.
Fryatt confidently fired his spot-kick low to the right, with Mildenhall diving the opposite direction, to spark celebrations from the visiting fans, although Fryatt was booked for over-celebrating his 30th goal of the season.
The Shrimpers blew a great chance to equalise when Barnard headed straight at Stockdale from a Francis free-kick.
And that error was punished in the 70th minute when Fryatt bagged his second of the match.
Dyer's curling free-kick from the right bounced back off the crossbar and Fryatt headed home from close range.
The Shrimpers pressed to find a way back in the match but were unable to find the vital goal.