Regular hard work; effectual service; excellent service whether in a good or bad cause. The reference is to the yeomen of the Free Companies.
“The whole training of Port Royal did him yeoman's service.” —Shorthouse Sir Percival, p. 56.
“We found a long knife, and a knotted hand-kerchief stained with blood, with which Claude had no doubt recently done yeoman's service.” —Miss Robinson: Whitefriars, chap. viii.
Source: Dictionary of Phrase and Fable, E. Cobham Brewer, 1894
More on Yeoman's Service from Infoplease: