In a one-sided second leg, the deadly strike force of skipper Alan Shearer and Patrick Kluivert shared the five goals on the night between them, in a clinical and positive display.
Newcastle will find out next Friday who will join them in the five-team group.
Perhaps the only surprise was that Sakhnin only had goalkeeper Energy Murambadoro sent off in the dying seconds after they had attempted to kick their opponents to bits.
The physical Israeli Premier Division side left Graeme Souness' men battered and bruised, but to their credit Newcastle refused to rise to the bait.
Murambadoro was shown a straight red card by lenient Spanish referee Rodriguez Santiago for handling outside the box to deny the hard-working Craig Bellamy a deserved goal.
Knowing an early goal would effectively kill off Sakhnin, United were in front after nine minutes with a cleverly worked strike. Jermaine Jenas worked a one-two with Kluivert and back-heeled the ball into the path of the Dutchman, who added to his two goals from the first leg.
Sakhnin, now needing four goals to win, were offered some hope when their best player Alain Masudi scored four minutes later from close range - but there was to be nothing else for them.
They tried hard to unsettle Newcastle with some appalling challenges, but United answered them back in the best possible way with two more goals before the interval.
A horrendous blunder for Murambadoro gift-wrapped United the lead again after 38 minutes. There seemed little danger when a speculative shot from the left by the superb Lee Bowyer was unexpectedly spilled and Shearer gratefully rammed in the rebound.
An end-to-end move after 42 minutes saw Laurent Robert pick out Kluivert, who again finished with style.
Souness sent on Steve Harper for Shay Given at the break, and the keeper watched as Masudi needlessly fouled Jenas to concede a penalty. Shearer allowed the keeper to commit himself before sticking the spot-kick in the opposite corner.
Fit again Darren Ambrose and James Milner were given a run out before Murambadoro was red carded.
From the free-kick following that incident Bowyer saw an effort wrongly disallowed for offside.
But United were not finished. Having used their three substitutes, Sakhnin were forced to put Khalec Khalaileh in goal, but he could do nothing to prevent Shearer from completing his hat-trick in the last minute from the edge of the box.
It rounded off another great European night for Newcastle and saw Shearer take his European goals haul for the club to 20.