Leda Valladares nació en Tucumán en 1919. Su padre fue tucumano mientras que su madre era una "patricia" santiagueña de apellido Frías, bisnieta de Félix Frías, y su adolescencia transcurrió entre el blues, el jazz y la música clásica que escuchaba su padre. «Antes de mirar el mundo me puse a oírlo. Por mi padre, tocando y cantando entré al follaje de la música», dijo.

Se graduó en la Universidad Nacional de Tucumán con el título de profesora de filosofía y luego también se licenció en Ciencias de la Educación.

Antes de cumplir los veinte años, formó su primer grupo de música, con unos amigos: FIJOS (Folclóricos, Intuitivos, Jazzísticos, Originales y Surrealistas). Con el seudónimo de Ann Key comenzó a cantar jazz. Pero en esa época, la música era casi un juego y Leda cuenta que ella cantaba en inglés por fonética (pese a su irreductible pasión por la música folclórica argentina también mantuvo toda su vida una gran pasión por el jazz, música de la cual era apasionada desde los catorce años).