Pittsburgh Penguins vstoupili do NHL v sezóně 67-68 jako jeden ze šesti nově příjmaných klubů. Pittsburgh dlouho nepatřil k místům, která by přitahovala oči nedočkavě bloudící po hokejové mapě. Velké hokejové hvězdy se spíše Pittsburghu vyhýbaly a ani ti, kteří měli peníze, neměli velký zájem investovat do ledního hokeje. A to i přesto, že již před více jak šedesáti lety se zde hokej hrál a mužstvo s názvem Pirates reprezentovalo tehdy třetí americký tým NHL. V sezóně 69-70 se dostali až do semifinále Stanleyova poháru. Byla to sezóna, ve které vynikl střední útočník Michel Briere se 44 body. Po skončení ligové sezóny však Briere zahynul při automobilové nehodě a trvalo dost dlouho, než se černý mrak nad mužstvem rozplynul. V následujících letech se stali Penguins hrozbou pro ostatní týmy především díky útočnému pojetí své hry, které v té době uplatňoval útok ve složení S. Apps ml., J. Provonost a L. MacDonald. Tento útok jako druhý nejlepší v NHL nastřílel v ročníku 73-74 soupeřům celkem 107 gólů. Dalšími hráči byli brankář Denis Herron, obránce Randy Carlyle a útočníci Pierre Larouche a Rick Kehoe, který dokud se neobjevil Lemieuxe, držel klubový rekord s 55 góly nastřílenými v sezóně 80-81.

Novodobá historie Pittsburgh Penguins začala 9. června 1984 kdy si klub vybral Maria Lemieuxe jako hráče číslo jedna v Draftu NHL.  Mario Lemieuxe, který byl již v té době pasován za nástupce Wayne Gretzkyho, začal tyto prognózy velmi záhy naplňovat, ale ve svém úsilí zůstával příliš osamocen, takže se týmu stále nedařilo odpoutat ode dna Patrick Division, v té době nejvyrovnanější v NHL. Mario se v první sezóně stal nejlepším nováčkem soutěže a jeho přítomnost na ledě znamenala o 35 bodů více. O rok později již o čtyřicet bodů. Hokej v Pittsburghu, který nedlouho před Lemieuxovým příchodem uvažoval o azylu někde u sousedů, prožil nebývalou renesanci. Hvězda formátu Lemieuxe začala táhnout, a když pomyslně posadil Mario na svoji hlavu korunu nejlepšího hráče NHL, kterou nosil Wayne Gretzky, Penguins zatroubili k útoku.

 K prvnímu zlepšení došlo v sezóně 88/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 74/75 (tehdy obsadili třetí místo Norris Division). Ve Stanley Cupu 89 však postoupili jen do čtvrtfinále, což byl ale přece jen velký úspěch po šesti letech absence v play-off. 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 89/90 vstupovali Penguins s opravdu silný 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ž byla hlavní tíha odpovědnosti, a jeho jedenadvacetizápasová absence však vrátily klub na dno ligové tabulky. V divizi skončil na pátém místě a v celé NHL obsadil až sedmnáctou pozici.

Před nastávající sezónou 90/91 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 B.Trottiera a talentovaného J.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 golmana T. Barrasa. 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 pak 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, a 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 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. Hlavní podíl na zisku Stanley Cupu 91měla bezesporu vedle nejlepšího hráče závěrečných kol play-off M. Lemieuxe trojice Recchi, Coffey, Francis, která soupeřům nastřílela 85 branek v základní části ligové soutěže. Sám Recchi se čtyřiceti brankami se stal čtvrtým nejlepším střelcem NHL.

Od jubilejního 75. ročníku NHL si "tučňáci" slibovali mnohé, ale už v úvodu sezóny je postihla rána nejtragičtější. Jejich kouč a miláček celé hokejové Ameriky-Bob Johnson-zemřel. Naštěstí našel Pittsburgh náhradu v muži ještě povolanějším. Po čtyřech letech se z "důchodu" vrátil Scotty Bowman, nejúspěšnější trenér historie NHL. V Pittsburghu však měli i problémy existenčního rázu. Jejich majitel nechtěl stále jen doplácet na nákladnou činnost úspěšného týmu a jednu chvíli to dokonce vypadalo, že se Pittsburgh s NHL rozloučí. Naštěstí se našel nový majitel - bývalý šéf WHA H. Baldwin - a hráči se mu odvděčili tím nejkrásnějším způsobem - obhajobou Stanley Cupu. Ve finále porazili Chicago Black Hawks 4:0 na zápasy. V následující sezóně dokonce poprvé v historii zvítězili v základní části NHL, ale pokus o hattrick ve Stanley Cupu nevyšel. Ve čtvrtfinále play-off 93 překvapivě podlehli New Yorku Islanders v prodloužení sedmého zápasu. Rozhodující branku Islanders vstřelil David Volek.

Po zranění páteře a po svém vítězném boji proti Hodgkinově nemoci se Mario Lemiuexe v sezóně 93-94 vrátil na led a stihl ještě první kolo play-off kde však byli Penguins vyřazeni Washingtonem Capitals. Nemoc a únava donutila Maria vynechat sezónu 94-95, ve které cesta za Stanley Cupem skončila pro Penguins ve druhém kole na New Jersey Devils.

V sezoně 95-96 pak opět udivovala Lemiuxova úžasná technika a báječná spolupráce s Jaromirem Jágrem která znamenala vice než jednu třetinu soupeřům nastřílených branek. Stejně plodný v útoku byl i Ron Francis. Stal se třetím "tučňákem", který překročil hranici 100 bodů v sezóně. Generální manažer Patrick sestavu Penguins střídavě měnil mladými talenty. Patřil k nim obránce Sergej Zubov a střední útočník Petr Nedvěd. Oba tyto hráče Patrick získal od New York Rangers výměnou za Luca Robitaillea a Ulfa Samuelssona. Jejich pouť v play-off skončila nečekaně ve třetím kole na Floridě Panthers.

Ročník 96-97 skončil pro Penguins v prním kole play-off kde ztroskotali na ambiciozním týmu Philadelphia Flyers. Tato série byla také posledním vystoupením Lemieuxe na ledě NHL neboť Mario uskutečnil svůj avizovaný konec hráčské kariéry.

Sezóna 97-98 byla uspěšná pro Jaromíra Jágra, který ziskem Art Ross Trophy,  potvrdil svou vůdčí roli v týmu po odchodu Maria Lemiuexe. V prvním kole play-off byli Pittsburgu nad síly hráči Montrealu Canadiens.