Απολιθώματα γνήσιων Εμβιοπτέρων είναι σχετικά νέα και χρονολογούνται στο τέλος της κρητιδικής περιόδου και στην αρχή της παλαιογενούς περιόδου. Το παλαιότερο γνωστό είδος είναι το Sorellembia estherae από το κεχριμπάρι της Βιρμανίας, το οποίο χρονολογείται στη μέση Κρητιδική. Τα απολιθώματα αυτά εμφανίζουν πλέον τους χαρακτήρες των σύγχρονων Εμβιοπτέρων. Υπό συζήτηση είναι πολύ παλαιότερα ευρήματα από την Περμια περίοδο, που δείχνουν μόνο ένα μέρος των χαρακτηριστικών των σημερινών Εμβιοπτέρων και τα οποία ίσως ανήκουν σε προγόνους αυτών. Οι ειδικοί συμφωνούν πως η τάξη κατατάσσεται στην ομάδα ""βλατοειδή-ορθοπτεροειδή"", (Βλαττοειδή, Μαντώδη, Ισόπτερα, Δερμάπτερα, Πλεκόπτερα, Γρυλοβλαττοειδή, Φασματώδη, Μαντοφασματώδη και Ορθόπτερα), αλλά διαφωνούν για τις σχέσεις μεταξύ αυτών των τάξεων.