The song became a major hit for Sarah Vaughan in 1959, peaking at #7 in the Billboard Charts and #5 on the R&B charts. This version was released by Mercury Records under catalog number 957085. The song was also released in the UK, where it first entered the charts on September 11, 1959, and spent 11 weeks there, also peaking at #7.
Despite the record's commercial success, Vaughan herself always thought the song to be corny. However, "Broken Hearted Melody" was to become one of her most popular hits, giving Vaughan her first gold record. It also became part of her concert repertoire for many years afterwards.