The critics at Metronome magazine received Maxine's first records warmly, giving the discs good ratings and reviews. Around the same time Maxine became the vocalist at The Onyx Club in New York. It was here that she formed both a music and personal partnership with bass-man John Kirby who she soon married. Kirby had worked with Fletcher Henderson in the early 1930’s as well as Henry Red Allen. A busy man in 1937, the stellar bassist recorded with Teddy Wilson, Willie The Lion Smith, Frankie Newton, Midge Williams, Charlie Barnet, and Lionel Hampton all prior to the first records he made with Maxine on August 6th, 1937 which also saw accompaniment from Thornhill on piano. Sullivan and Kirby remained married until 1941.

It was this first session with Kirby that proved to be both a blessing and a curse for Maxine Sullivan. It produced a hit record, a swing version of a Scottish folk song called Loch Lomond. Unfortunately it "typed" her and she depended on similar folk style performances for many subsequent records, despite her ability to adapt to other forms of Pop and jazz songs equally well. Her cool, soft, tone and subtle and intimate style was equally swinging on records like Nice Work If You Can Get It, Blue Skies, St Louis Blues, and Stop Your Breaking My Heart. Unfortunately there were a bevy of records like Darling Nellie Gray, Annie Laurie, Molly Malone and others that began to sound all very similar.

In 1940 Sullivan and Kirby were featured on the radio program Flow Gently Sweet Rhythm. They were the first black jazz stars to have their own weekly radio series. Sullivan and Kirby’s last shows together were in the fall of 1941 and were recorded by two different transcription companies, World and Associated. In the mid 1940s she was recorded with the bands of Teddy Wilson, Benny Carter, and Jimmie Lunceford and can be heard singing mainly ballads with all three groups.

Aside from sessions with Ellis Larkins and Bob Haggart, her recorded output was little until 1955 and 1956. Finally recorded singing better material in the company of musicians like Dick Hyman, and old cohorts Buster Bailey, Charlie Shavers, and Russell Procope; Sullivan produced a series of sides that were her most exciting since her 1937 sessions. In the late 50’s she branched out to new areas of study, in nursing and playing valve trombone, which she played at numerous concerts and festivals in 1958. From 1958 to 1966 nursing took up her career. In ’66 she reemerged playing several festivals with her new husband pianist Cliff Jackson. From then until 1986 she continued to appear at festivals and can be heard with musicians from Doc Cheatham to Scott Hamilton. Her last recorded concert was at The Fujitsu-Concord Jazz festival held in Tokyo in September of 1986.

Maxine Sullivan appeared in the movies St. Louis Blues and Going Places, the latter opposite of Louis Armstrong. On stage, she was seen in Swingin’ The Dream in 1939, and Take A Giant Step in 1953. She toured Great Britain in 1948 and again in 1954. In her later concert appearances she traveled to France for several performances in 1984 and to Sweden many times beginning in 1975 and ending in 1984. Maxine Sullivan died in April of 1987, little more than one month short of her 76th birthday and just 8 months after her last recorded concert appearance. The last song she performed at the Fujitsu – Concord Jazz Festival and her last performance on record…was Loch Lomond.