She reluctantly agreed to headline in the Big Rhythm Show of 1952, a British concert package kicking off in London with the Cab Calloway orchestra and dancer Marie Bryant. Though she had not expected to stay abroad beyond the two-week tour, she remained in Europe for two years, with London and Paris as her main locations. Williams' disappointment surfaced when it became apparent that the concerts were closer to British variety than a serious presentation of jazz. Tight British musicians' union rules, she realized, would stymie opportunities to more fully develop her English audience as she had first hoped.

However, Williams had second thoughts about returning to the U.S. Her fluency in traditional and modern jazz delighted her fans and opened doors to additional engagements and recordings. Melody Maker writer Max Jones, who befriended Williams after her arrival, helped her bypass union rules for appearances with British bandleader Ted Heath at the Palladium in January 1953. Around that time she also recorded the first a series of recordings for Vogue and performed in concert with Sarah Vaughan. At Max Jones' urging, she collaborated with him on an 11-part autobiographical writings for Melody Maker. She declined an offer from manager Joe Glaser to perform European dates with Louis Armstrong and the All-Stars in favor of plans (later scaled down) for a big band tour of the continent.

Concerts in Paris and Holland in June 1953 helped convince her to relocate in November to the French capital, where (she later wrote) she was happiest. There were no union rules in France to inhibit her music making. Williams was also overjoyed to meet up with old friends like tenor saxophonist Don Byas.

She moved into the Hotel Cristal on the Left Bank, where she kept company with such fellow luminaries as writers James Baldwin and Chester Himes, actor Canada Lee, singers Eartha Kitt and Annie Ross, and Baron Timme Rosenkrantz and his companion Inez Cavanaugh. It was also in Paris that she first met Baroness Nica de Koenigswarter and Nicole Barclay. Her Vogue recordings with Byas demonstrated that bop no longer dominated her playing, but had been fully absorbed into her style.

She performed for radio and television across Europe, but work was sporadic and money problems aggravated her psychological instability. One benefactor—Col. Edward Brennan—showed Mary a small Catholic church with walled garden and statuary. "I found God in a little garden in Paris," she later recalled. Her depression deepened and, at one point she walked off a night club stage. When she returned to New York on December 15, 1954, it was with the vow that she would quit performing.