Alicia robló un contratu de prueba con Jermaine Dupri y So So Def Recordings, onde apaeció na portada del álbum navidiegu interpretando «The Little Drummer Girl». Coles mesmes, mientres esta dómina coescribió y grabó el cantar «Dah Dee Dah (Sexy Thing)», que formó parte de la BSO de la película Men in Black (1997). Esta tema foi la primer composición profesional dAlicia, anque nunca foi llanzada como single dau los conflictos de los representantes dAlicia con Columbia, que llevaríen finalmente a la fin del so contratu. Alicia taba insatisfecha col tratu que la compañía diéralu mientres los dos años del contratu, pos la so carrera enllancárase al escarecer duna direición determinada. Alicia púnxose entós en contautu con Clive Davis, que sintió que satopaba ante una artista especial y única y consiguió-y un contratu con Aresta Records, compañía que más tarde seslleiría. Mientres esta dómina Alicia tamién adoptól que seríal so nome artísticu: anque nun principiu inclinóse por Alicia Wildeel so mánager suxuriólu quusara Keys por cuenta de un suañu que tuvo, conseyu que la cantante aceptó. Alicia siguió trabayando con Davis na so nueva compañía J Records, onde trabayó con Kerry Krucial Brothers y grabó los cantares «Rock wit O» y «Rear View Mirror», que fueron utilizaes nes BSO de les películes Shaft (2000) y Dr. Dolittle 2, respeutivamente. 