En 1966, Celia y Tito Puente empecipiaron una asociación queditó cinco álbumes musicales. Tamién grabó álbumes cola Orquesta de Memo Salamanca, Juan Bruno Tarraza y una placa discográfica con Lino Frías, toos ellos so TICO Records. Estos álbumes nun algamar tanto ésitu como sesperaba, pero unu quotru númberu sí tuvo ampliu espardimientu, como yel casu de Bemba Colorá. Sicasí, dempués dello, Cruz xunir a Vaya Records. Un cambéu musical facer ingresar a la salsa. En 1973, aliar col pianista y artista esclusivu del sellu disquero FANIA, Larry Harlow y encabezó un conciertu de música afrocubana nel Carnegie Hall de Nueva York. Ellí Celia Cruz interpretó Gracia Divina, el so primer cantar de salsa y la puerta a esti nuevu ritmu. Lálbum resultante desti alcuentru foi producíu pol yá desapaecíu Jerry Masucci y quien ye consideráu unu de los creadores del xéneru salsa xuntu al músicu dominicanu Johnny Pacheco. Darréu, participó nun llexendariu conciertu grabáu en direuto nel Yankee Stadium con The Fania All-Stars, un conxuntu integráu por líderes de grupos llatinos que grababen pal sellu Fania.