Born Anita Belle Colton in Chicago, Illinois on October 18, 1919, O’Day got her start as a teen. She eventually changed her name to O’Day and in the late 1930’s began singing in a jazz club called the Off-Beat, a popular hangout for musicians like band leader and drummer Gene Krupa. In 1941 she joined Krupa’s band, and a few weeks later Krupa hired trumpeter Roy Eldridge. O’Day and Eldridge had great chemistry on stage and their duet Let Me Off Uptown became a million-dollar-seller, boosting the popularity of the Krupa band. Also that year, “Down Beat” magazine named O’Day “New Star of the Year” and, in 1942, she was selected as one of the top five big band singers.
After her stint with, Krupa, O’Day joined Stan Kenton's band. She left the band after a year and returned to Krupa. Singer Jackie Cain remembers the first time she saw O’Day with the Krupa band. “I was really impressed,” she recalls, “She (O’Day) sang with a jazz feel, and that was kind of fresh and new at the time.” Later, O’Day joined Stan Kenton’s band with whom she cut an album that featured the hit tune And Her Tears Flowed Like Wine.
In the late’40s, O’Day struck out on her own. She teamed up with drummer John Poole, with whom she played for the next 32 years. Her album Anita, which she recorded on producer Norman Granz’s new Verve label, elevated her career to new heights. She began performing in festivals and concerts with such illustrious musicians as Louis Armstrong, Dinah Washington, Georg Shearing and Thelonious Monk. O’Day also appeared in the documentary filmed at the Newport Jazz Festival in 1958 called Jazz on a Summer Day, which made her an international star.