New Notts Manager Paul Ince was forced to change the team as he was without the likes of Craig Westcarr, Lee Hughes and Neal Bishop. This allowed a return to left-back Stephen Hunt and on-loan winger Alan Judge, with Karl Hawley starting again upfront.
The Manager took the applause from the fans in the directors box minutes shortly before kick-off.
It was the visitors who had the first chance of the game when the former Spurs striker Lee Barnard shot narrowily over the bar, but Notts were top in the early exchanges with Ben Davies' crossing ability causing all sorts of chaos in the Saints penalty box.
Nine minutes in the Magpies took the lead when Mike Edwards rose highest from a Davies corner and powered in a superb header past Kelvin Davis. The centre-back had orignially called for a short-corner, but raced back into the box to score his first goal of the season.
Calls of "Incey give us a wave" came from a packed Kop as the atmosphere hotted up and quietened down the 2,000 or so Saints fans.
An excellent intervention by midfielder John Spicer, who beat two lunging challenges from the opposition, set up another attack, sadly his through ball to Hawley didn't quite reach his desired target.
Edwards headed wide from another Davies corner and Ricky Ravenhill also tested Davies in goal as Notts continued to dominate. Ince's side tempo in the first twenty minutes had certainly upset the Saints.
Another set-piece delivery from Davies could have brought a penalty as both Edwards and Krystian Pearce were left in a heap at the back post, but the match official match turned down the Notts appeals.
Minutes later Southampton's Ricky Lambert beautifully curled a free-kick around the wall, but the scoreline stayed 1-0 as the post saved Notts.
The incident's didn't stop as Notts raced clear only for a poor Alan Judge pass allowed a Southampton defender to break up another attack and as the game's tempo didn't drop captain John Thompson excellent last-gasp slide tackle on Barnard. The game was becoming tastier and tastier as the challenges flew in.
It was the Saints fans who felt aggrieved when a powerful shot hit a Notts player, the away following bellowed out their disappointment, but once again the ref waved away any appeals.
Slippery winger Jason Puncheon slipped as he turned and shot and his effort went well wide on the 40th minute.
The visitors came more involved in the match with goalkeeper Rob Burch commanding his area with a series of punches and claims.
Half Time - Notts County 1 Southampton 0
The second half began scrappily with both teams finding it hard to get the ball on the deck. Great pressure from Hawley nearly doubled Notts' lead, but his charge down from the Saints goalkeeper went wide.
Saints should have equalised when Lallana crossed the ball low to Dean Hammond who was in acres of space, the goalscorer Edwards managed to do enough to put the opposition captain off as it was deflected wide.
It was the Notts fans with there head in there hands when a dangerous Ben Davies was brilliantly saved, and then from the clearance Judge's powerful shot hit Karl Hawley which could have easily hit the back of the net, but sadly went over the bar.
Davies was again the architect when he whipped in a free-kick only for captain Thompson to head over.
The Saints were given a penalty when Thompson upended Barnard. The captain was then given a red card to the dismay of the Kop. It seemed as he had played the ball. It was a harsh decision.
Striker Lambert stepped up and cooly shot low past Burch on the 68th minute.
Assistant Manager Alex Rae who communicated with Manager Ince via mobile phone as Jon Harley moved back to full-back and Hunt moved in to centre half.
Moments later Ravenhill headed off the line as the Saints piled on the pressure. From the resulting corner Notts didn't clear the corner and Lambert picked up the ball inside the penalty box and calmly squared the ball accross the face of the goal to his strike partner Barnard to tap in. Two goals in a five-minue spell.
Striker Luke Rodgers was brought off the bench to try and grab an equaliser, but it was Harley next to test the 'keeper who volleyed into the arms of Davies.
The Saints wrapped up the three points when the dangerous Lallana curled in a shot past Burch from 25-yards-out.
The Magpies continued to battle, with excellent strong challenges from Pearce and Lee, but the five minute spell in the second half was so vital and Notts were on the wrong side of the key decision of the match for the penalty and the sending off.
Attendance: 9.547 (2,229 away fans)
Man of the Match: Mike Edwards
Listen to every match this season and watch all the highlights and interviews on Magpie Player.