At the age of seventeen, Bailey moved to Seattle and worked as a sheet music demonstrator at Woolworth's. She married and divorced Ted Bailey, keeping his last name because she thought it sounded more American than Rinker.[3] With the help of her second husband, Benny Stafford, she became an established blues and jazz singer on the West Coast. According to Gary Giddins' book Bing Crosby – A Pocketful of Dreams – The Early Years 1903-1940, in 1925 she secured work for her brother, Al Rinker, and his partner Bing Crosby. Giddins further states that Crosby first heard of Louis Armstrong and other Chicago black jazz records from Bailey's own record collection. Crosby helped Bailey in turn by introducing her to Paul Whiteman. She sang with Paul Whiteman's band from 1929-33 (According to Gary Giddins, Whiteman had a popular radio program and when Bailey debuted with her version of "Moaning Low" in 1929, public reaction was immediate, although she did not start recording with Whiteman until late 1931).

Her first two records were as uncredited vocalist for an Eddie Lang Orchestra session in 1929 ("What Kind O' Man Is You?", an obscure Hoagy Carmichael song that was only issued in the UK) and a 1930 recording of "I Like To Do Things For You" for Frankie Trumbauer. She was Whiteman's popular female vocalist through 1932 (recording in a smooth crooning style), when she left the band due to salary disagreements. She then recorded a series of records for Brunswick in 1933 (accompanied by The Dorsey Brothers), as well an all-star session with Benny Goodman's studio band in 1934 that featured Coleman Hawkins.