Magpies' caretaker boss Ian Richardson's re-shaped side got his tenure off to a great start with a 3-0 home win - only their second of the season - over Shrewsbury Town.
With both sides locked dangerously near the bottom of League Two the game showed the significance of a six-pointer and Richardson knew that he had a tough baptism only 48 hours after his appointment.
Just as the first half looked set to drift to a goalless conclusion, Paul Bolland headed in from close range for his first Notts goal since September 2003.
The 39th minute effort should not have been the first goal of the game as Shrewsbury striker Luke Rodgers squandered a guilt-edged opportunity on the half-hour mark by firing wide of an open goal, while Shrews' keeper Scott Howie produced a brilliant tip over on 38 minutes to deny Gavin Gordon.
Shrewsbury had plenty of possession after the break and battled tenaciously for an equaliser, but they were punctured by Notts' second goal on 70 minutes. Howie could only parry a low swerving effort by Stefan Oakes and Glyn Hurst pounced for his 10th goal of the season.
Shrewsbury were reduced to ten men when defender Darren Moss, who had been cautioned in the first half for dissent was sent off 10 minutes before the end for serious foul play - a straight red card.
As a result County wide man Chris Palmer had a little more room when fed by Oakes seconds from the end and he lashed an absolute rocket past Howie.
In the end Notts were fully deserving of the three points but they have certainly found Shrewsbury tough opposition and the difference in finishing between the two sides was as crucial as anything else.