Dakota Staton was born in Pittsburgh, Pennsylvania and studied music at Pittsburgh's Filion School of Music. She was soon chosen to be a vocalist with the Joe Wespray Orchestra, then the top band in the Pittsburgh area. After spending two years with Wespray she traveled to Detroit, working in various clubs there. Staton then followed the nightclub circuit which led her to Canada, Indianapolis, Minneapolis, St. Louis, Cleveland, and eventually New York.
It was while singing in a Harlem nightclub called the Baby Grand that Capitol Records producer Dave Cavanaugh discovered Staton and signed her to the label. After several singles Staton attracted the attention of Down Beat magazine, winning the magazine's high profile Most Promising New Comer Award in 1955. In the late 1950s she rose rapidly in popularity due to some fine swinging vocals on her first full length Capitol Records LP as backed by Jonah Jones on trumpet in 1957. The title track of this release turned out to be her biggest all time hit: The Late, Late Show. It was during this session that Staton also recorded her superb vocal rendering of what had previously been an instrumental hit for Count Basie called Broadway.