K prvnímu zlepšení došlo v sezóně 1988-89, kdy se pittsburským podařilo vyšplhat na druhou příčku své divize, což jim v součtu celé NHL vyneslo šesté místo, kterým si zopakovali své nejlepší ligové umístění ze sezóny 1974-75 (tehdy obsadili třetí místo v Norrisově divizi). Ve Stanley Cupu 1989 však postoupili jen do čtvrtfinále, což byl ale přece jen velký úspěch po šestileté absenci. Nový generální manažer klubu – Tony Esposito – mohl být s výsledky své práce spokojen. Jako bývalý brankář velmi dobře věděl, že od tohoto postu se odvíjí hra celého týmu, a proto při rozsáhlých nákupech hledal především kvalitního gólmana. A toho našel v Tomu Barrassovi. Do sezóny 1989-90 vstupovali Penguins s opravdu silným týmem. Kapitánem byl Lemieux, v obraně hráli prim Paul Coffey a Zarley Zalapski, v útoku John Cullen, Rob Brown, Kevin Stevens, Mark Recchi a Phil Bourque. Zranění Maria Lemieuxe, na němž ležela hlavní tíha odpovědnosti, a jeho jedenadvacetizápasová absence však vrátily klub na dno ligové tabulky. V divizi Penguins skončili na pátém místě a v celé NHL obsadili až sedmnáctou pozici. Před nastávající sezónou 1990-91 proto došlo pochopitelně k výměně "kormidelníků". Tonyho Esposita nahradil na postu manažera Craig Patrick, který doplnil tým o veterána Bryana Trottiera a talentovaného Jaromíra Jágra. V hráčské výměně s Hartfordem získal středního útočníka Rona Francise, stejně dobrého v útočné i obranné hře. Obranu vyztužil Larry Murphy , který měl čistit prostor v brankovišti pro gólmana Barrassa. Na místo kouče byl angažován Bob Johnson, devětapadesátiletý muž, který přivedl v roce 1986 tým Calgary Flames do finále Stanley Cupu.

S takto posíleným kádrem se chtěl Johnson pokusit poprvé zvítězit v divizi. Zranění zad Maria Lemieuxe se však ukázalo natolik vážné, že vůbec nemohl nastoupit. To byla nečekaná ztráta, která zapříčinila, že se tým opět potácel na dně tabulky. Když už to vypadalo, že Pittsburgh ani tentokrát nepostoupí do play off, vrátil se Lemieux na led, aby i přes své bolesti pomohl týmu k postupu. Ačkoli nastoupil jen v šestadvaceti zápasech, nasbíral skvělých 45 bodů, ale hlavně vlil do svalů svých spoluhráčů tolik nových sil, že se zrodil historický úspěch Penguins. S náskokem tří bodů před New York Rangers vyhráli Patrickovu divizi a na cestě do finále Poháru postupně vyřadili New Jersey Devils 4:3 na zápasy, Washington Capitals 4:1 a Boston Bruins 4:2, i když v této sérii už prohrávali 0:2. Ve finále proti Minnesotě nenechali nikoho na pochybách a zvítězili 4:2 na zápasy, přičemž v posledním utkání deklasovali Severní hvězdy 8:0.