Coleostraca (lit. "sheathed shells") is a branch of the clade Stenostraca.
Coleostraca first appeared around the year 4185ma, developing into the first terrestrial macropredators. The shell of ancestral Diplostoma is realized as an internal "gladius", which serves as a site of muscle attachment and making Coleostraca the only branch of Anthostoma to have developed internal support. The gladius grants Coleostracans greater speed than other Diplostomes
The appearance of Dromaeopoda led to the extinction of many species of Coleostraca. Some of the surviving species evolved into the Elastospondyli branch, a clade of which would become the Opisthoptera.