Kluivert had struck twice in the first-half, but that was as good as it got for the Magpies, who now face a tricky second-leg in Tel Aviv with just a two-goal advantage.
Souness opted for an attack of Kluivert and Shola Ameobi, leaving Alan Shearer and Craig Bellamy on the bench with one eye on Sunday's trip to former club Southampton.
And Kluivert opened the scoring with just two minutes and 52 seconds on the clock.
The Holland striker, who opened his United account in Sir Bobby Robson's last game in charge at Aston Villa, was quickest to react after Laurent Robert's ball into the box resulted in a goalmouth scramble.
A minute later Jermaine Jenas should have doubled Newcastle's advantage, but his low shot was turned wide by visiting goalkeeper Energy Murambadoro.
With Souness sitting in the directors' box, his assistant Alan Murray was forced into an early change, with Aaron Hughes unable to continue after he was on the receiving end of a heavy challenge a couple of minutes into the game.
He was replaced at left-back by fit-again Olivier Bernard, who missed United's win over Blackburn Rovers with an ankle injury.
Sakhnin defended deeper and deeper as the half went on and Kieron Dyer did not help Newcastle's cause by drifting inside from his right wing position at every opportunity, leaving unexploited space on the wing.
The visitors, meanwhile, had their first shot on target in the 28th minute, with Suan forcing Shay Given into a decent save. Two minutes later Murambadoro was in action, tipping a Lee Bowyer shot wide.
Dyer had the next chance, with the England international somehow shooting over from five yards after Robert had put the ball into the box.
However, Kluivert made no mistake in the 41st minute from a Robert corner, putting a bullet header past Murambadoro and off the crossbar and post, just as the crowd were growing restless with Newcastle's lack of progress.
Seconds after the break Bowyer should have done better, shooting weakly at Murambadoro from ten yards.
Dyer pulled up was replaced by England team-mate Butt in the 58th minute, the second enforced change of the game for Souness. But worse was to come for Newcastle seconds later a scything challenge from Bassam Ganayem on Jenas.
The home players were enraged and just a minute later Suan prevented Butt from taking a quick free-kick. The England midfielder reacted by grabbing Suan by the throat, sparking a fracas that involved half a dozen players. The incident left the Portuguese referee with little option but to show the former Manchester United midfielder and Suan red cards.
The niggling continued and minutes later Bowyer was booked for going clean through Alain Masudi. Next Avi Danan was shown a yellow card for a brutal challenge on Ameobi, with Sakhnin showing little interest in playing football.
James Milner then replaced Ameobi, leaving Shearer and Bellamy to watch the rest of the game on the bench with Souness having used all his three substitutes.
The youngster almost provided Kluivert with his hat-trick but a defender just managed to flick the ball clear of the Dutchman's head, leaving United with just a two-goal cushion to take to Israel in a fortnight's time.