It is known that it was a comedy (according to Francis Meres's Palladis Tamia, Wits Treasury). Meres also lists Shakespeares others comedies: Ge'tleme' of Verona, his Errors, his Love labors lost, his Love labours wonne, his Midsummer night dreame, & his Merchant of Venice : for Tragedy his Richard the 2. Richard the 3. Henry the 4. King John, Titus Andronicus and his Romeo and Juliet. So it is known it is not one of these.
For a period of time it was thought to be The Taming of the Shrew, however in 1953 Pottesman discovered the August 1603 booklist of the stationer Christopher Hunt which listed Marchant Of Vennis, Taming Of A Shrew, Loves Labor Lost, Loves Labor Won.