A number of Shakespeare's plays were published as quarto editions (so-named because the paper was folded twice, make four pages on one side of a sheet of paper) during his lifetime. These individual editions had no "category" listed, though they often contained words like history or tragedy in the title, e.g. The Most Excellent and Lamentable Tragedy of Romeo and Juliet, The Tragedy of King Richard the Third, or The History of Henry the Fourth.
The arrangement of the plays into the three categories is a practice
begun with the First Folio, which was printed in 1623, seven years after
Shakespeare's death.