Hi.
There are not many mantid species known from fossils, but the available data suggest that modern mantids did not appear in numbers before the Tertiary, although according to molecular data most groups were already present in the Cretaceous. This is a bit of a riddle. Since the best fossils are amber mantids, one explanation is that only small species living on bark were small enough and lived in the "right" habitat to be encompassed by resin. This also explains why this type of "primitive" mantid is still abundant in the Eocene amber fossils, although "higher" mantids were already common. And, indeed, the only higher mantids known so far from amber are small nymphs. Some mantodean type fossils are known as compressions in stone, but these are mostly wings and are the object of some dispute among scentists.
Greets,
C.