There seems to be a number of different sources from which Shakespeare pulled to create The Two Gentlemen of Verona.
First, there is a pastoral romance novel Diana Enamorada, in which Shakespeare’s characters of Julia, Proteus and Silvia find analogs in Don Felix, Felismena, and Celia. Don Felix sends a letter to Felismena, who pretends to reject it through her lady-in-waiting. Felix is sent away by his father, and Felismena journeys to follow her love (disguised as a boy), and is later hired on by Felix as his page. She learns that Felix has fallen in love with another woman, Celia, and Felix uses his new hire to be his messenger to Celia. Celia wants nothing to do with Felix, but falls in love with the boy (the disguised Felismena). In the woods, after a battle, Felismena and Felix are reunited; Celia dies of a broken heart (there is no Valentine character). The novel was written in 1542 in Spanish by a Portuguese writer Jorge de Montemayor. Though it wasn’t translated into English until 1582, it’s possible that Shakespeare may have read the earlier French translation, or might have absorbed it through an earlier English version (no longer extant), The History of Felix and Philomena, which was produced in the mid-1580s.
Second, Shakespeare might have been influenced by Thomas Elyot’s The Boke named the Governor (published in 1531), which in turn may be been influenced by (or outright taken from) Boccaccio’s The Decameron. In these source materials, Titus and Gisippus (the analogs for Proteus and Valentine) are childhood friends. Gisippus falls in love with a woman, but when he introduces the woman to Titus, Titus plans to steal the woman from his friend. Gisippus, however, sets up a “bed trick” allowing his friend to sleep with his betrothed on their wedding night, so that the girl becomes his friend’s actual wife.
Third, Shakespeare also seemed to pull some ideas from The Tragical History of Romeus and Juliet by Arthur Brooke (yeah, the source for Romeo and Juliet), which features a character named Friar Laurence and the use of a “corded ladder” to steal away the female love interest.