Mstislav Rostropovich had studied composition with Shostakovich and abandoned his course in 1948 when his teacher was dismissed from the Conservatory. He hoped for years for a concerto; Shostakovich's wife advised him never to mention the subject. The score was begun on 1 May 1959 and finished on 20 July at the composers' retreat in Komarovo. Rostropovich learned it in four days and played the premiere in Leningrad that October. The four-note motto that opens it is built from the composer's DSCH monogram, and a distorted Georgian song favoured by Stalin appears in the finale.
Shostakovich traced the impulse for the piece to Prokofiev's Sinfonia concertante, written a few years earlier for the same cellist, and said in June 1959 that he was planning the concerto in three movements. In the finished score the cadenza became a movement in its own right rather than an episode inside one, and the concerto is dedicated to Rostropovich.