It leaves United in a great position for next Thursday's second leg at St James' Park and a place in the last 16.
Alan Shearer summed up the feelings of the United camp when he said: "We felt there was nothing in it in the first half and only a defensive mistake from ourselves gave them the impetus.
"We did a very professional job and we always knew that our superior fitness would tell.
"We scored two very good goals and I was delighted with mine. It was a tremendous ball in from Patrick (Kluivert) and I managed just to stay on-side and I struck it sweetly.
"We are now looking forward to the second leg next Thursday."
United created an early fourth minute opening when Stephen Carr got free on the right but Lee Bowyer got under his cross and headed well over the bar.
Heerenveen - who had finished fourth in their league in two of the last three seasons - hit back and Mika Vayrynen produced a similar effort to that of Bowyer when he too got under the ball and headed over after eight minutes.
The first yellow card arrived after ten minutes when Swede, Petter Hansson, crudely challenged Shola Ameobi from behind and was fortunate not to get a second soon afterwards following another rash tackle on Shearer.
Souness must have been pleased the way his side had started, though at the same time frustrated at the lack of a cutting edge against a nervous-looking home defence.
Shola Ameobi headed down for Bowyer - who had scored twice on this ground for Leeds against Partisan Belgrade when they were forced to play at a neutral venue - but his tame effort went woefully wide.
Not for the first time this season and indeed during his United career, Titus Bramble must shoulder responsibility for the goal that put Heerenveen ahead after 25 minutes.
The central defender was far too easily brushed aside by Dutch international Arnold Bruggink on the left of the area and when he pulled the ball back, Klaas-Jan Huntelaar cleverly turned Amdy Faye to smash a left-footed drive in off the bar.
United had to wait until the 26th minute for their first shot on target with Celestine Babyaro's effort doing little to bother Brian Vandenbussche.
Seconds later and the defence once again went AWOL and danger man Huntelaar was given a free header that he placed at Shay Given.
United's best opportunity of the half arrived five minutes before the break when Carr's deep cross was headed back across goal by Shearer, but Ameobi made a total hash of his close-range effort that he somehow conjured to head wide.
Whatever Souness said at the break worked wonders, that was however after Bramble made a last-gasp challenge to deny Huntelaar and Bruggink drove the clearance narrowly over.
United clearly grew in confidence as the game progressed and Bowyer fired wide after great work from the marauding Carr.
Ameobi made way for Laurent Robert and Kluivert revelled in the forward position alongside Shearer.
Two great balls from the Dutchman signalled the United revival. After 66 minutes, the former Ajax and Barcelona man played in Shearer, who was denied by a superb Said Bakkati block and Carr lashed the rebound inches over.
But three minutes later United were celebrating through goal machine Shearer with his 13th goal of the season and sixth in Europe.
Robert charged forward to pick out Kluivert who played a deft pass into the path of Shearer who advanced to the edge of the area and smashed United level.
Heerenveen were stunned and noticeably, United took full advantage to grab the all-important winner.
Robert hit a magnificent crossfield pass for Kluivert who patiently held up the ball waiting for Carr to make ground on the right.
When the former Spurs man played in the ball Kluivert got the slightest of touches and Bowyer did the rest, backheeling the ball beyond the stunned Vandenbussche.
Bowyer turned from hero to zero late on when he was shown a needless second yellow card for an unnecessary handball.