Liverpool almost threw away the points here at Anfield, after powering into a 3-0 lead just after the first half hour.
Over the following 30 minutes, they allowed Salzburg to get back to 3-3 before re-energising and collecting all the points thanks to Salah's decisive second goal in this game.
The reds were without Joel Matip who suffered a knock at the weekend - with Joe Gomez in to replace him.
Salzburg had already scored 6 goals in their first game against Genk, and before kick off Genk's 0-0 result with Napoli suggested that perhaps that first result should be looked upon with respect.
And so it proved in this game. Group E is going to prove much trickier than most fans probably thought when the draw was made.
Mane opens the scoring
Liverpool were off and running in the 9th minute when Andy Robertson's pass found the feet of Sadio Mane. He ran towards the area, exchanged a beautiful one-two with Bobby Firmino, and then lifted the ball around the keeper to keep up his impressive goalscoring stats in this competition.
Ten minutes later it was 2-0. And a second LFC goal for Andy Robertson. He brought the ball from his own half, exchanged passes but carried on into the area. By the time Trent Alexander-Arnold sent the ball across, it was Robbo who was standing at the edge of the 6 yard box and stuck it away with the skills of a traditional number 9.
With ten minutes of the first half remaining, Mo Salah finally got himself a goal. He had missed an earlier chance from a Fabinho through ball, but this time it was a simpler tap in. Mane crossed the ball low from out wide, and Firmino arrived near post with a header. Stankovic in the Salzburg goal parried it away from his goal, only to place it in to the path of the Egyptian.
A comfortable 3-0 lead? Not quite.
Salzburg fight back
With a few minutes of the first half remaining, Salzburg got one back.
Hee-Chan Hwang turning van Dijk inside the area before belting his shot past Adrian.
Second half never really started right for the reds. Flat atmosphere in the stands was matched by one on the pitch and it was no big surprise when in the 55th minute, Salzburg got a second. Hwang involved again, his cross came out to the edge of the area and there were no defenders located near Takumi Minamino who lashed it across Adrian and into the corner of the net.
3-2 now, and an excellent time for Salzburg to bring on Haaland who grabbed a hat-trick in the first group game.
Within 3 minutes of coming on he had scored the equaliser, a simple tap in unmarked in front of goal after a cross was sent over low across the face of goal.
Klopp made attacking changes. Milner and Origi replacing Henderson and Wijnaldum. Liverpool couldn't settle for one point after the opening defeat to Napoli.
For the final 30 minutes Liverpool did step back up the gears and took more control of this game - perhaps embarrassed by how the game had played out.
Firmino provided a hat-trick of assists when he sent the ball onto Salah who scored what would prove to be the winning goal on the night.
Towards the end the result began to look secure and Keita was eventually brought on for a brief cameo against one of his former clubs.
The similarities with last season's group stage are continuing. The reds now take on Genk in the next two games, away first, and will be hoping that the outcome of those two games will leave the reds in a very strong position to qualify from the group. But this Group E is not a walk in the park.
Video Highlights - Liverpool 4-3 FC Salzburg