The opera was composed between March 1867 and July 1868, and it received its first performance on 11 February [OS January 30] 1869 at the Bolshoi Theatre in Moscow. It was a benefit for Alexandra Menshikova.
In the 1870s Tchaikovsky destroyed the manuscript full score of the opera, while recycling much of the first act in his The Oprichnik (1870–1872). The subject of The Voyevoda was thus left available to his former pupil Anton Arensky to compose as the opera Dream on the Volga in 1888. During the Soviet period The Voyevoda was posthumously reconstructed from surviving orchestral and vocal parts and the composer's sketches.