Leicester's players appear in touring records starting in 1558-9 as Lord Robert Dudley's players (REED PP); their patron wrote a letter referring to them in June of 1559 (Wickham 205). The company continued with Dudley's patronage when he became the earl of Leicester in 1564. The troupe was at court during Christmastide in 1560-1 and 1561-2. They are in provincial touring records from 1564-72, frequenting the Midlands as well as routes to the East, South, and West as they had the previous five years (REED PP). There is a chance that the company performed at the Red Lion in 1567-8. If so, one of their plays was The Story of Samson.
In 1572 Leicester's players petitioned their patron requesting that they be made "household servants" officially (to protect them in light of the Vagrancy Act of 29 June 1572). Six players signed the petition: James Burbage, John Perkin, John Laneham, William Johnson, Robert Wilson, and Thomas Clarke. On 10 May 1574, the company received a patent, which further protected their status as a company. The petition named the above players excepting Clarke. The company continued to tour regularly on their familiar circuits with at least one trip North to Newcastle on Tyne. However their escalating prominence is noticeable in two other areas: court and London. The company appeared at court for nine straight Christmastides, 1572-3 through 1581-2, and the following titles are linked to them in the Revels Accounts: Predor and Lucia, Mamillia, Philemon & Philecia, Panecia, The History of the Collier, A Greek Maid, and a comedy called Delight. They probably also had The Three Ladies of London (Q1584), which was written by their player, Robert Wilson. In London it is reasonable to assume that Leicester's players performed at the newly built Theater due to their long association with James Burbage, who, using the money of his brother-in-law, John Brayne, built the playhouse in 1576.
In March 1583 the Queen's players were formed, and Leicester's lost at least three players to the new organization: Johnson, Laneham, and Wilson. Yet the company continued to tour, and it appeared at court on Shrove Sunday (10 Feb) a month before its loss of players and in 1586-7. By that time the company had acquired several players who turn up in later companies: William Kempe, George Bryan, and Thomas Pope. Others named include Daniel Jonns, Thomas King, Thomas Stevens, and Robert Percy. The latter players were listed along with Kempe, Bryan, and Pope as members of a troupe touring on the Continent as Leicester's players. Leicester's Men disappear from theatrical records in 1588, the year of the earl of Leicester's death (4 Sept).