1958's Black, Brown, and Beige features the incomparable Mahalia Jackson, whose rendition of "Come Sunday" is not only one of the most lyrical, tragic, and majestic moments in American music, it is also the most substantial religious statement in all of jazz. There has never been a religious singer of Jackson's technique, depth, and breadth featured on a jazz recording, and there has never been a jazz orchestra as great as the one Ellington brought to the studio on that occasion. "Come Sunday" is Ellington's musical prayer for the civil rights movement and Jackson delivers it with the kind of purity that can only be heard as a wonder.

Anatomy of a Murder (Columbia Legacy, 1959), written for Otto Preminger's film, is considered (correctly) by writer Tom Piazza to be "a vernacular American symphony," in which the central themes are investigated with such refined variation and subtleties of color, and the piece evolves so successfully from track to track, that listening is an increasingly satisfying experience.

"Idiom '59" from the 1959 Festival Session (Columbia Legacy)—the single essential gem from the recording—is further proof of how well Ellington and Strayhorn had mastered theme and variation, melodically, harmonically, and in terms of timbre and rhythm.

"The Queen's Suite," was written for Elizabeth II in 1959. There was originally only one pressing given as a gift to the (inevitably charmed) monarch. After Ellington's death, it was released as part of The Ellington Suites (Pablo).