Detroitban született igen kiszolgáltatott körülmények között. Anyja tizenhét éves volt és alkoholista, amikor Sheila megszületett. Pennsylvaniában nagyszülei vették magukhoz. Az apját csak néhányszor látta egész életében.
A nagypapa szintén alkoholista volt. Ennek ellenére a nagyszülők rendesen próbálták nevelni a kislányt, de egy komfort nélküli házban laktak, más családokkal együtt.
A gyerek szívesen hallgatta az új énekeseket a rádióban, a zenei memóriája pedig olyan nagyszerű volt, hogy hallás után szinte mindent elsőre meg tudott jegyezni. Nyolc éves korában már színpadra mert állni. Az iskolában és a templomban is énekelt.
Az 1940-es negyvenes években kezdte foglalkoztatni a dzsessz. A drákói szigorú nagynénje adott neki zongoraórákat. Sheila kis méretű kezei nem értek át a kellő szélességben a billentyűket, és ha melléütött, a nagynéni ütött. Ez nem tarthatott sokáig.
Jordan az ötvenes években New Yorkba költözött és elmerült a dzsesszben. Lennie Tristano, Charles Mingus, és a későbbi férje, Juke Jordan volttak a mesterei. Charlie Parker oda volt Jordan abszolút hallásáért, és „millió dolláros fül”-nek becézte.
Sheila Jordan egyre inkább nem érezte otthon magát a többségükben komoly drogfüggő zenészek között. A kor Amerikájában tombolt a faji megkülönböztetés, a rendőrség zaklatta a szórakozóhelyek főként fekete vendégeit, akikkel ő sokat és szívesen volt együtt.
George Russell(wd) egy nap elhatározta, hogy foglalkozni fog Sheila gazdag, tiszta és rezignált hangjával. Russel arra a szenvedésekkel teli gyerekkorban elsajátított tisztaságra volt kíváncsi, ami mélyen ott rejtőzött Sheilában. Amit Sheila Jordan George Russelltől megtanult, azt az énekesnő művészetében végleges megőrizte.