Her extended family, with five-year-old Mary and her sister in tow, moved to Pittsburgh, which offered opportunities to all newcomers as America entered World War I. The introspective young girl was already looking to music to assuage her loneliness and early experiences with racism. By age eight, "the little piano girl of East Liberty," as she had become known, was regularly playing for parties, wakes, silent films, and, at least on one occasion, in a brothel. She, influenced by early records of Fats Waller and James P. Johnson, had already developed a pleasing repertoire of waltzes, marches, sentimental ballads, ragtime and light classics. She first tasted the life of a traveling musician at thirteen, when a visiting show,"Buzzin’ Harris and His Hits and Bits," suddenly lost its pianist. Enlisted as a successful replacement,

she hit the road with this latter-day version of the hardscrabble tent shows that traversed rural America in the nineteenth century when the leader of the show's band, saxophonist Johnny Williams, persuaded her mother to let her go, since school was out for the summer. A notary was called, as Williams recalled, "and papers were signed because I was underage."

Johnny Williams would soon become Mary's first husband, and his little band, the Syncopators, got a big break as accompanists to the dance team of Seymour and Jeanette James—among the few such black acts then touring on a major vaudeville circuit. When young Seymour died suddenly of a heart attack in 1926, Jeanette bravely tried to carry on, but Johnny Williams, with whose band Mary Lou had made her recording debut, now decided to join the band of T. Holder and turned leadership of his own Memphis-based band to his wife. When Holder was fired by his sidemen for financial finagling, they appointed bassist Andy Kirk as leader and renamed the band "The Dark Clouds of Joy." Kirk made Kansas City their headquarters, and Mary Lou joined her husband there—a move that ultimately led her—and the Kirk band—to national prominence.