When the previous Gilbert and Sullivan opera, Ruddigore, finished its run at the Savoy Theatre, no new Gilbert and Sullivan opera was ready, and for nearly a year the stage was devoted to revivals of such old successes as H.M.S. Pinafore, The Pirates of Penzance and The Mikado. For several years leading up to the premiere of Yeomen, Sullivan had expressed the desire to leave his partnership with W.S. Gilbert in order to turn to writing grand opera and other serious works full-time. Before the premiere of Yeomen, Sullivan had recently been lauded for the successful oratorio The Golden Legend and would produce his grand opera, Ivanhoe, only 15 months after Yeomen.
In the autumn of 1887, after another attempt to interest his collaborator in a plot where the characters, by swallowing a magic pill, became who they were pretending to be (Sullivan had rejected this idea before), Gilbert made an effort to meet his collaborator half way. Gilbert claimed that the idea for the opera came to him while he was waiting for the train in Uxbridge and spotted an advertisement for The Tower Furnishing and Finance Company, illustrated with a Beefeater. On Christmas Day, 1887, he read to Sullivan and Carte his plot sketch for an opera set at the Tower of London. Sullivan was "immensely pleased" and, with much relief, accepted it, writing in his diary, "Pretty story, no topsy turvydom, very human, & funny also".
Although not a grand opera, Yeomen provided Sullivan with the opportunity to write his most ambitious score to date. The two set to work on the new opera, taking longer to prepare it than they had taken with many of their earlier works. Gilbert made every effort to accommodate his collaborator, even writing alternative lyrics to some songs. Sullivan had trouble setting one lyric in particular, "I have a song to sing-O!", with its increasing length in each stanza. He asked Gilbert if he had anything in mind when writing it. Gilbert hummed a few lines from a sea shanty, and Sullivan knew what to do.
The first act was rather long and contained an unusual number of sentimental pieces. As opening night approached, Gilbert became increasingly apprehensive. Would the audience accept this serious, sentimental tone from one of the duo's "comic" operas? Gilbert and Sullivan cut two songs from Act I and part of the Act I finale, partly to decrease the number of sentimental pieces near the beginning of the opera. Gilbert, always nervous himself on opening nights, came backstage before the performance on opening night to "have a word" with some of the actors, inadvertently conveying his worries to the cast and making them even more nervous. Jessie Bond, who was to open the show with a solo song alone on stage, finally said to him, "For Heaven's sake, Mr. Gilbert, go away and leave me alone, or I shan't be able to sing a note!"