Although it may not have seemed it at the time, the 2-0 defeat at Preston sparked an incredible journey for the ex-West Ham boss in charge of the Blues.
Promotion to the Premier League, consecutive top-nine finishes, an FA Cup triumph, and a first European campaign were all achieved under his stewardship – across two spells.
Here’s what we’ve selected as the 75-year-old’s greatest matches as Fratton chief.
Message From the Editor
You can support our local team of expert Pompey writers by subscribing here for all the latest news from Fratton Park for less than 25p per week.
9. Wigan 1-2 Pompey (29-04-2006)
Premier League safety was secured with an excellent comeback against Wigan. Henri Camara had given the hosts the lead, before Benjani scored his first goal in 15 appearances to equalise. Matt Taylor then remained composed to slot home a penalty which ensured the Blues would be competing in the top-flight the following season. Picture: :Jonathan Brady Photo: Jonathan Brady
10. Pompey 2-1 Manchester United (07-04-2007)
Pompey recorded a shock victory over the league leaders to blow the title race wide open. Matt Taylor opened the scoring when he pounced on Benjani's rebounded effort to fire home, before a comical own goal by Rio Ferdinand gave the Blues a 2-0 lead. David James then ensured the hosts would collect three points when he denied Alan Smith late on after John O'Shea halved the score. Picture: Barry Zee Photo: Barry Zee
11. Pompey 7-4 Reading (29-09-2007)
The 11-goal thriller at Fratton Park is still the highest scoring match in Premier League history. Benjani netted a hat-trick during the victory in the rollercoaster fixture on the south coast. The striker had given Redknapp's side a two-goal advantage before the visitors levelled the scores. Chaos then ensued, as Hermann Hreidarsson put the hosts back in front before the Zimbabwean grabbed his third and Nico Kranjcar and Sulley Muntari got in on the act -- either side of a Ivar Ingimarsson own goal. Shane Long's strike and Sol Campbell's own goal saw the match written into top-flight tapestry. Picture: Barry Coombs Photo: Barry Coombs
12. Newcastle 1-4 Pompey (03-09-2007)
A barnstorming Pompey rout on the road. Three goals in the first three minutes at St James' Park saw the visitors end the Magpies' home unbeaten run on their way to another top nine finish. Kranjcar's inch-perfect second half free-kick completed the rout. Picture: Nigel French Photo: Nigel French