Desde sus inicios en la música, Héctor Lavoe grabó un total de once discos al lado de Willie Colón, incluyendo los dos últimos álbumes, The Good, The Bad, And The Ugly(1975) y Vigilante (1983).
En 1967, Willie tenía listo la mitad de su primer álbum para el sello Alegre Records y Futura Records, pero estas disqueras quebraron y el material fue confiscado, aunque luego el ingeniero de sonido Irv Greenbaum los obtuvo y se los llevó a Jerry Masucci. Ya luego, el sello Fania Records le ofrece a Willie Colón grabar para este sello con la condición de cambiar al cantante de esa orquesta que era Tony Vásquez,21 ahí es donde Johnny Pacheco propuso a Héctor Lavoe como nuevo vocalista de la orquesta de Colón, Pacheco ya estaba al tanto de su voz, su enunciación impecable y sus habilidades estilísticas. Para aquel entonces Colón era considerado un joven músico de propuestas interesantes pero con mal sonido.
En una de esas presentaciones que daba la orquesta de Willie en los locales latinos de Nueva York, se encontraba tocando The New Yorkers, la orquesta donde cantaba Héctor Lavoe. Pacheco y Colón fueron a ofrecerle a Lavoe que terminara de grabar ese álbum, recibiendo una respuesta negativa en un primer momento aunque luego aceptaría concluir el LP.
Muchos años después, Willie Colón comentó en una entrevista cómo conoció a Héctor Lavoe.
“Cuando me ofrecieron grabar para el sello Fania, no lo creí. Cuando conocí a Johnny Pacheco, lo primero que me dijo fue: hay que buscarte un cantante... Yo en ese momento tocaba en el Club de la Legión Americana, en la 162 y Prospect Avenue, y en el piso de arriba, el Ponce Social Club, tocaba otra orquesta: The New Yorkers. Ellos tenían un cantante jovencito, jincho, feo y flaco. Se llamaba Héctor Juan Pérez Martínez. Fui con Pacheco a ofrecerle que grabara con nosotros ese primer disco. Para mí era duro, porque mi cantante llevaba años conmigo. Lo peor fue que Héctor me contestó bien guapetón: Yo no quiero grabar contigo, man... Ustedes están bien, bien flojos. ¿Por qué se negó? Con el tiempo me dijo, despechado, que fue porque en aquel momento no le había ofrecido entrar en la orquesta, sólo grabar. Héctor y yo entendimos que nuestro junte fue algo necesario y natural.
En el verano de 1967 salió al mercado su primer trabajo discográfico, llamado El Malo, en donde Héctor, quien ya era conocido como "La Voz" (LaVoe), aparece como vocalista líder cantando los temas «Borinquen», «El Malo», «Chonqui» y «Quimbombo». Las otras canciones de este álbum fueron interpretadas por Yayo El Indio y Elliot Romero, quienes ya habían grabado algunos temas antes de que Willie Colón firmara por Fania Records.23
Lavoe mencionó haber ingresado a la orquesta de Willie en condición de invitado, sin algún tipo de contrato:
Desde esa vez para adelante (después de haber grabado El Malo), no le dije a Willie que iba a tocar con él; nunca hablamos de negocios, nunca se dijo nada [...] Esos temas los hice bien, según ellos [...] Yo tenía 17 años y Willie tenía 15, era un nene... Desde que hice el LP, nunca hablamos de trabajar con el grupo, pero metí mano. Él me dijo: "estamos tocando estas semanas en el Red Garter, en el Corso y en otros lugares", y me invitaron a todos los sitios a los que iban a tocar. Trabajé porque sucedió y pasó, eso fue estar en el sitio y al momento en que se necesitaba.
Al año siguiente, en 1968, se publica The Hustler el segundo álbum de Lavoe al lado Colón. Para aquel entonces, Héctor no cantaba en inglés por lo que se convirtió en el vínculo de la orquesta de Colón con lo caribeño; el trombonista decidió aprovechar el potencial que brindaba el cantante para decantarse definitivamente hacia la música latina afroantillana.24 En este LP destacaron los temas «Qué Lío», «Se Acaba Este Mundo» y «Eso Se Baila Así».25 Durante ese año (1968), Lavoe inició una relación sentimental con Carmen Castro, quien quedó embarazada, pero se negó a casarse con él porque lo consideraba un mujeriego. El primer hijo de Lavoe, José Alberto Pérez nació el 30 de octubre de 1968. Cuando José fue bautizado, Héctor recibió una llamada informándole de que Nilda Puchi Román (con quien también tuvo una relación) estaba embarazada. El segundo hijo de Lavoe, Héctor Jr. nació el 25 de septiembre de 1969. Después de esto, la pareja se casó, y tras una petición de su esposa, Héctor se mantuvo alejado de su primer hijo y la madre de este.15 Para ese tiempo, el sello Fania decide crear una orquesta con los artistas más conocidos e importantes que albergaban, a menudo, reforzados por estrellas invitadas procedentes de otros sellos de música latina y de otros estilos. Esta orquesta recibió el nombre de Fania All Stars.
El primer concierto de Lavoe con la Fania All Stars se dio en el Red Garter Club en Greenwich Village del cual se editaron dos volúmenes: Live at the Red Garter, Vol. 1 en 1968 y Live at the Red Garter, Vol. 2 en 1969 . Este concierto contó con temas más instrumentales y la mayoría de las canciones fueron en inglés. Una de las pocas canciones cantadas en español fue «Noche» con las voces de Pete "El Conde" Rodríguez, Ismael Miranda, Adalberto Santiago y Héctor Lavoe.
En 1969 se lanza el álbum Guisando (Doing A Job), el primer disco en donde Lavoe comparte créditos con Colón y aparece en la portada. Este sería la primera vez que el binomio Colón-Lavoe mostraría sonidos más cercanos a la guaracha, el son, la guajira y el guaguancó con fusiones atrevidas e ingeniosas proponiendo un estilo agresivo e irreverente de hacer música. De este álbum destacan los temas «Guisando», «No Me Den Candela» y «Te Están Buscando».26
Para fines de 1969, se publicó el álbum Cosa Nuestra (Our Thing)27 en donde se nota la consolidación de la dupla salsera como una de las mejores bandas de la escena latina de Nueva York, el disco al igual que los anteriores cosecharía éxito entre el público latino y gran parte del mundo salsero. Canciones como «Che Che Colé», «Juana Peña», «Te Conozco» y el bolero «Ausencia» son solo algunos de los temas presentes en este álbum que se convirtieron en éxito inmediato. Su música comenzaba a pasar fronteras y ya se oía con fuerza en países como Panamá, Perú, Venezuela, Colombia, algunos países del Caribe, Europa y América Latina.28
La carrera artística de Héctor Lavoe continuó con la publicación de su quinto trabajo al lado de Willie Colón, La Gran Fuga (The Big Break), de donde se desprendieron temas como «Ghana' E», «Sigue Feliz», «Barrunto » y «Panameña»,29 siendo esta última, un pequeño homenaje de la dupla salsera a Panamá, país que siempre los recibía con mucho cariño. Éste álbum fue lanzado al mercado en octubre de 1970.
Su éxito era tal que constantemente eran contratados por algunos países de Latinoamérica para presentarseante multitudes.
Asalto Navideño sería el siguiente álbum de Lavoe y Colón, grabado en la primera semana de diciembre de 1970 con el objetivo de ser lanzado y promovido durante la Navidad de ese año.30 La fusión musical que logró Willie al experimentar con los sonidos típicos de Puerto Rico, en especial con el aguinaldo, la bomba y la plena, junto al cuatro de Yomo Toro y la interpretación de Lavoe, hizo que el álbum se convirtiera sin lugar a dudas, en el mejor disco navideño grabado por orquesta alguna de música latina-caribeña hasta la fecha. Los temas que destacaron de este álbum son «La Murga», «Traigo La Salsa» y «Canto A Borinquen» tema dedicado al país natal de Lavoe; Puerto Rico.31 Desde el momento que salió a la venta, este se convirtió en uno de los álbumes más importantes de la dupla
El éxito de estos álbumes, transformó significativamente las vidas de Colón y de Lavoe. La banda de Colón ofreció un crudo y agresivo sonido de trombones que fue bien recibido por los fanáticos de la salsa y Lavoe complementó el estilo, con su voz articulada, talento para la improvisación y sentido del humor. Héctor recibió un reconocimiento inmediato, trabajo estable, y el dinero suficiente para proporcionarse un cómodo estilo de vida.
Según el propio Lavoe, todo pasó tan rápido que no sabía cómo lidiar con el éxito repentino.
El año 1971 significó una serie de presentaciones en donde la voz y carisma de Lavoe atraían público al igual que los trombones de Colón, que se volvió uno de los instrumentos más típico de la salsa, algo que funcionó muy bien para este binomio salsero. Sin embargo, Lavoe comenzó a consumir drogas, a llegar tarde a los conciertos y a llevar una vida de excesos que comenzó a hacer mella en su indiscutible talento por lo que tuvo que someterse a varias rehabilitaciones. En agosto de ese año (1971), la Fania All-Stars reestructurada y con artistas de su propio sello, se presentó en el Club Nocturno Cheetah ubicado en la esquina sudoeste de la calle 52 y la avenida 8, este club que Ralph Mercado ayudaba a administrar en los años 1960 presentó a artistas de rock y R&B como Jimmy Hendrix, James Brown y Aretha Franklin;33 en esta presentación, Lavoe interpretó junto a todos los cantantes de Fania los temas «Quítate Tú», «Estrellas de Fania» y «Qué Barbaridad», este último al lado de Ismael Miranda. Este concierto dio origen a dos álbumes: Live at the Cheetah, Vol. 1 y Live at the Cheetah, Vol. 2, ambos publicados el año siguiente, en 1972.