Dudfield scored twice and made the other for substitute Hector Sam as the Magpies hit three times after the break to secure their passage into the hat.
The scoring was opened shortly after the break as Dudfield thundered home, before Sam's second 25 minutes later.
Dudfield then rounded off the win after a brief scare by dispossessing visiting goalkeeper Danny Naisbitt and tapping home with two minutes left.
The score was perhaps not a fair reflection on Histon of the Blue Square Premier who hit a bar, forced a superb save from Notts custodian Kevin Pilkington and were the better side in the opening half.
Notts boss Charlie McParland left Myles Weston out of the squad after the winger missed the latter training sessions in the week proceeding, owing to a family bereavement while Stephen Hunt's knock at Barnet kept him sidelined, allowing Adam Tann the captaincy.
Tann was partnered in the defence by new loan acquisition Krystian Pearce while Andy Parkinson came in for Weston.
Histon, sitting seventh in the division below Notts, arrived at Meadow Lane having won their past four games earning manager Steve Fallon the Blue Square Premier Manager of the Month gong for October, started the better in their bid for a cup shock.
With former Cambridge United legend John Beck as a coach, it was clear the way the non-leaguers were to play and their long ball tactic was causing problems for Notts as numerous high balls weren't cleared.
Luckily for the Magpies a lack of any real finishing effort kept Pilkington's goal secure.
To an outsider, it wouldn't have appeared to be FA Cup first round day, with the quiet atmosphere and a game that was something of a non-starter but it suddenly burst into a bit of life after 15 minutes.
First the dangerous Erkan Okay worked his way down the wing and crossed to Antonio Murray whose effort looked as if it would creep inside Pilkington's post, but the Notts man just tipped it for a corner.
Then Parkinson, wasteful in possession all half, hit a hopeful long range effort straight at Naisbitt with team-mates better placed.
The reports coming from Histon recorded them as a threat from set-pieces, and Fallon's side certainly forced there fair share of corners which Notts defended well, Pearce in particular showing all the authority of an established professional - not a 17-year-old making his competitive debut.
Captain Adrian Cambridge continued to take most of the dead ball situations, including his long-throws and one was met by the head of defender Matthew Langston whose flick nearly hit the target, but with no attacker ready to pounce, Notts survived.
The home faithful were growing slightly concerned as Notts' midfield were being bypassed by both sides back four, and Histon were perfecting their game plan better than their League Two counterparts.
The Magpies' first shot on target didn't come until five minutes before the
That it was the only time Naisbitt was forced into a save in the first period highlighting that Histon weren't going to roll over and die and Notts needed an immediate improvement after the break, and got it.
Just three minutes into the second half Dudfield times his run to perfection and the previously flustered MacKenzie perfectly weighted a ball through the centre for Dudfield to latch onto, and waste no time in blasting past the onrushing Naisbitt into the roof of the net.
It was a dream start to the second half and much needed, with nerves likely to start creeping in the longer Histon continued to enjoy as much possession as they did in the opening half.
Now a real cup tie was developing, with Histon again doing most of the pushing, but it was clear that Notts did hold the extra class and the counter-attack was proving a good weapon.
Parkinson was again well fed in space but he again didn't make the most of it, tamely hitting at Naisbitt from just inside the box.
After 55 minutes McParland signalled for Sam to enter the action for the tireless Lindfield, and his introduction was to cause extra panic for the Histon rearguard.
Luckily for Notts it fell to six-goal top scorer Richard Butcher but he somehow hit the side netting with the goal gaping.
Dudfield shot over from the edge of the box soon after, before Pearce headed wide from a short corner.
With the game becoming a bit edgy, a clash of heads right in front of the dugout saw Lee Canoville harshly booked with the Histon bench up in arms at his tackle that they saw as deliberate, to the amazement of the majority in the crowd.
Matt Somner entered the field on 71 minutes, replacing the tiring MacKenzie who now departs for Germany on Monday for a hernia operation, and Somner's first action was to help Notts defend the best move of the match.
Right from the back Histon showed they can also play on the deck, with two or three neat passes leading Okay to lay the ball into an unmarked Murray in the box, but he is brilliantly denied by Pilkington when it seemed certain he'd bring the visitors level.
And Murray was left to rue that miss as Notts broke down the other end through Dudfield.
The former Boston United man worked his way into the far corner but somehow held possession and twisted through no fewer than three defenders to work his way into the penalty area where he squared for Sam, who despite lacking the real connection, managed to divert home for a deserved goal.
Somner tried to get in on the act with a left footed effort from 25 yards but Naisbitt did well to turn it wide, before Parkinson wasted another chance shooting over.
Histon were denied a deserved consolation when Langston headed against the bar in front of the Kop with six minutes left, to deny a grandstand finish.
Instead it was left to Notts to add another goal to their tally as Dudfield made it three in three for him after a long barren spell when he nipped in front of Naisbitt following a short back pass, and rounded him to tap home.
That was Dudfield's last piece of action as recent virus victim Spencer Weir-Daley replaced him with three minutes of injury time given.
That saw no action and Notts now await the draw for the second round, but not without a scare, knowing that their better class in the final third just saw them through.