Con el equipo sufriendo problemas económicos, parecía que la franquicia de Pensilvania bajaría la persiana o viajaría a otra ciudad Pittsburgh registró el peor récord de la liga tanto en la temporada 1983 como en la 1984. Mario Lemieux, una de las elecciones de draft más esperadas en la historia de la NHL, debía ser seleccionado en el Entry Draft de la liga de 1984. Entrando al final de la temporada por encima de los New Jersey Devils, últimos, los Penguins realizaron varios movimientos cuestionables que parecieron debilitar el equipo en el corto plazo. Registraron tres rachas de seis partidos sin ganar en los últimos 21 partidos de la temporada y se ganaron el derecho de elegir a Lemieux en medio de las protestas de la dirección de los Devils.
El entrenador de Pittsburgh, Lou Angotti, admitió después que se tomó una decisión consciente de terminar la temporada como el equipo con el peor récord. Angotti declaró que una comida a mitad de la temporada motivó el plan, porque existía una gran posibilidad de que la franquicia cerrara si Lemieux no era seleccionado. Otros equipos ofrecieron considerables paquetes de traspaso por la elección de draft, pero los Penguins se quedaron la selección y escogieron a Lemieux primero absoluto.
Lemieux dio sus frutos enseguida y anotó en su primer disparo de su primer shift de su primer partido en la NHL. Sin embargo, el equipo pasó cuatro años más fuera de los playoffs tras su llegada. A finales de los 80, los Penguins rodearon a Lemieux finalmente de un fuerte reparto secundario, traspasaron por el defensa superestrella Paul Coffey desde los Edmonton Oilers e incorporaron talento joven como los anotadores Kevin Stevens, Rob Brown y John Cullen desde las menores. El equipo adquirió finalmente un portero de primer nivel con la suma de Tom Barrasso desde Buffalo.
Todo este talento tuvo un impacto inmediato a la hora de ayudar a Lemieux a liderar a los Pens, pero el equipo sufrió para alcanzar los playoffs. En la 1985-86, Pittsburgh se perdió las eliminatorias en el último día de la temporada por un partido. La siguiente temporada, no llegaron por sólo dos partidos y vieron como cuatro equipos con récords iguales o peores se clasificaban. En la 1987-88, por segunda vez, los Penguins se perdieron los playoffs por un partido.
Los mejores productos de los Penguins by Fanatics a tan solo un click de distancia.
En 1989, Pittsburgh rompió finalmente la barrera y llegó a las eliminatorias a cargo de Lemieux, que lideró la liga en goles, asistencias y puntos. Los Pens sorprendieron a los New York Rangers en un barrido de cuatro partidos en la primera ronda. Sin embargo, los Philadelphia Flyers los detuvieron en la segunda ronda.
Una hernia discal en la espalda de Lemieux recortó su temporada 1989-90, aunque aún amasó 123 puntos. Sin embargo, los Penguins desaparecieron del panorama de los playoffs. Optaron por reforzar su plantilla y apoyar a Lemieux en la offseason de 1990. Las firmas de agentes libres y los traspasos jugaron un papel importante en esto. Posiblemente, ningún movimiento fue más importante durante esta etapa que la selección de Pittsburgh de Jaromir Jagr con la quinta elección absoluta en el Entry Draft de la NHL de 1990.
La reforma de la plantilla surtió efecto y los Penguins ganaron su primer título de la Stanley Cup derrotando a los Minnesota North Stars en las Finales por la Copa en seis partidos. Pittsburgh remató su triunfo con una victoria por 8 a 0 en el partido decisivo, el margen de victoria más amplio en una final de la Stanley Cup en más de 80 años.
La siguiente temporada, el equipo perdió al entrenador Bob Johnson debido a un cáncer y Scotty Bowman asumió el cargo. Bajo Bowman, barrieron a los Chicago Blackhawks para repetir como campeones de la Copa en la 1991-92.
Los Penguins continuaron siendo un equipo formidable a lo largo de los años 90. Las estrellas de los años de las Stanley Cups fueron seguidas por delanteros como Alexei Kovalev, Martin Straka o Aleksey Morozov y los defensas Sergei Zubov, Darius Kasparaitis o Kevin Hatcher.
Pese a la salida de gran parte de las plantillas ganadoras de las Copas, Pittsburgh cultivó el talento suficiente para alcanzar la primera ronda de los playoffs en 1994, la segunda ronda en 1995 y las finales de conferencia en 1996. Las eliminatorias de 1997 marcaron un punto de inflexión, ya que los Penguins sufrieron una eliminación en la primera ronda a manos de los rivales Flyers en cinco partidos.