Bailey began by singing and dancing in Philadelphia's black nightclubs in the 1930s, and soon started performing in other parts of the East Coast.
ביילי התחילה את הקריירה שלה בשירה וריקודים במועדונים השחורים של פילדלפיה בשנות ה-1930, ועד מהרה החלה להופיע גם באזורים אחרים של החוף המזרחי.