Batesian mimicry is a relationship in which a harmful organism (the model) is mimicked by a harmless organism (the mimic), which gains protection because predators mistake it for the model. It is the most widely studied of mimicry complexes and has undoubtedly played an important role in the speciation of various animals especially insects. However, little is known about the early evolution of this important behavior and its evolutionary significance owing to a dearth of paleontological records. Here we report several specialized representatives of the family Alienopteridae from the Early Cretaceous of Brazil, mid-Cretaceous Burmite, and the Eocene of the USA. They exhibit unique morphological adaptations for wasp and ant mimicry and represent one of the oldest evidence of Batesian mimicry in the insect fossil record. Our findings reveal at least 65-million-year coevolution between extinct alienopterids and aculeates. Phylogenetic Bayesian network analysis houses Alienopteridae within Umenocoleidae explosively radiating similar to 127 Ma. Alienopteridae is the only Mesozoic-type cockroach family which passed IC/Pg.