United were stuck in a rut under the management of Jose Mourinho, while the French champions topped the toughest section of the group stages.
However, much has changed in the two months since. United go into Tuesday's first leg at Old Trafford on a run of 10 wins and one draw since Ole Gunnar Solskjaer replaced the sacked Mourinho.
PSG will have to cope without the injured Neymar for both legs of the tie due to injury and Edinson Cavani is also missing.
AFP Sports looks at five things Solskjaer has changed to give United hope of making the quarter-finals for the first time in five years.
Playing football the United way
"To win games you need to pass it forward and run forward." The basics under Solskjaer may seem simple but they contrast sharply with Mourinho's conservative approach that left a host of expensively assembled stars paralysed by fear of making mistakes.
The Norwegian spent more than a decade as a United player learning from Alex Ferguson and is trying to replicate the same aggressive, attacking approach ingrained in him by the Scot, who twice won the Champions League in charge at Old Trafford.
"It's a winning identity, it's a confident identity. We want to take risks. We want to go for the second, the third and the fourth goal because that's just how we do things at Manchester United," Solskjaer told Sky Sports.
Worryingly for PSG, it is not a naive approach solely based on bombing forward. Wins away at Tottenham and Arsenal in recent weeks exhibited United’s pace and firepower on the counter-attack, which could be the key to winning this tie.
Pogba leads way
While Mourinho butted heads with and routinely dropped Paul Pogba, Solskjaer has built his side around the French World Cup winner, with stunning results.
Pogba has scored eight goals and provided five assists in his past 10 games.
"Before the coach arrived I was in the shadows, on the bench, and I accepted that," said Pogba. "It is a pleasure to play again. Now I am always smiling."
The fact Marcus Rashford was rested at Fulham to keep him fresh for PSG, while Romelu Lukaku was handed a rare start says a lot for the change in his fortunes under Solskjaer.
The 21-year-old was never trusted with a consistent run of games as a central striker under Mourinho. In United's last European home game against Young Boys, the Portuguese coach did not hide his disgust when he missed an early chance.
No longer fearing the consequences of a missed opportunity, Rashford has scored six goals in eight starts since the change in management and finally looks set to deliver on his abundant potential.
Solskjaer outlined his first task as putting smiles back on the players' faces but the feel-good factor has galvanised the fans just as much as his squad.
Once a European fortress, United's three home games in the group stages produced just one goal and Sevilla also secured a rare away win in the Champions League to dump United out at this stage last season.
The decibel level has risen since Solskjaer’s arrival, even for humble opposition in Huddersfield, Bournemouth, Reading, Brighton and Burnley. PSG are the first big ticket of the new era and can be assured they will face a cauldron of noise.
Lindelof like a new signing
Mourinho spent most of his final season complaining that he had not been furnished with the experienced centre-back he demanded in pre-season, while chopping and changing his defence.
Solskjaer has put his faith in Victor Lindelof, who started the first 10 games under the new boss before being left out of Saturday's 3-0 win at Fulham to rest for Tuesday's challenge.
Confidence restored, the Swede has played a big part in United’s goals conceded dropping from 1.5 per game this season before Mourinho's departure to 0.6 per game since.