Protocoleopterans typically possess prognathous (horizontal) heads, distinctive elytra with regular window punctures, cuticles with tubercles or scales, as well as a primitive pattern of ventral sclerites, similar to the modern archostematan families Ommatidae and Cupedidae.

[2] Protocoleoptera was originally proposed by Robert John Tillyard in 1924 for the extinct genus Protocoleus, assigned to the family Protocoleidae.

[3] Roy Crowson later reused the name "Protocoleoptera" to refer to Early Permian beetles such as the Tshekardocoleidae, while establishing the Archecoleoptera for Late Permian beetles.

[5] Some authors reject the use of Protocoleoptera and Archecoleoptera and include their members within a broad concept of the suborder Archostemata instead.

[5][7] It is generally agreed that Tshekardocoleidae is the earliest diverging group among the major families.