They scored three goals before the interval through Pandiani , Valeron and Luque in the 5th, 34th and 44th minutes, respectively.
READ MORE: Watch Asamoah Gyan’s fleet of cars (Video)
A smart shot from the centre-forward Walter Pandiani, Deportivo's scorer at San Siro, a header from Juan Carlos Valeron and a fierce drive from Albert Luque a minute from half-time allowed Javier Irureta's team to wipe out Milan's first-leg advantage and leave them on course to progress on their away goal.
But the substitute and club captain Fran put them properly clear when he volleyed a fourth goal 14 minutes from time to give the Galicians an astonishing 5-4 aggregate win and take them into the tournament's semi-finals for the first time. There they meet Porto.
It was the first time a team has ever recovered from a three-goal first-leg deficit to win in the 12-year history of the Champions League and all the more impressive as it came against a Milan side who had not conceded a European goal away this season.
Deportivo La Coruna : Molina; Manuel Pablo, Romero, Naybet, Andrade, Mauro Silva, Sergio (Duscher, 87), Victor, Luque (Fran, 65), Valeron (Djalminha, 90), Pandiani.
Subs not used: Munua, Tristan, Capdevila,, Hector.
Booked: Victor, Pandiani.
Milan: Dida; Cafu, Pancaro (Rui Costa, 77), Nesta, Maldini, Pirlo (Serginho, 58), Seedorf, Gattuso, Kaka, Tomasson (Inzaghi, 67), Shevchenko.
Subs not used : Abbiati, Costacurta, Laursen, Brocchi.