Though the earliest mention of The Two Gentlemen of Verona is by Frances Meres in 1598, it is believed by many to be Shakespeare's first play, and therefore to have been written well before then. Theatres in London were closed from 1592 to 1594, which prompted Shakespeare to stop acting and start writing, so it may have been written then. Others date the play as early as 1587.

Its first recorded performance is in 1762, with actor-manager David Garrick.

An operatic version, with music by Henry Rowley Bishop ran for twenty-nine performances in 1821 and in 1895, it was staged by Augustin Daly at Daly's Theatre.

Early 20th century productions included a production in 1904 by Harley Granville-Barker, who also played Speed, at the Royal Court. The 1910 Stratford production was directed by F.R. Benson, who cast his middle-aged wife as Julia.

The most serious attempt to popularise the play was perhaps in 1926 when Robert Atkins staged it at the Apollo Theatre with John Gielgud as Valentine.

In 1960 Peter Hall, newly appointed artistic director of the RSC, chose to direct it as his first production. Other notable 20th century productions for the RSC include a 1970 production by Robin Phillips and 1991 production by David Thacker.