[1] Parastylotermes was first described by entomologists Thomas E. Snyder and Alfred E. Emerson in the 1949 paper Catalog of the termites (Isoptera) of the world.

Fossils of the species were recovered from the Middle Eocene, Lutetian, "Blue Earth" Baltic amber deposits, with three imagos and four isolated wings known.

Of the five known specimens, the original type series of fossils that von Rosen used in describing the species were held in the Bayerische Staatssammlung für Paläontologie und Geologie collections and are thought destroyed during World War II.

[3] P. frazieri was the third species of Parastylotermes to be described and is known from a single wing collected in 1954 by T. H. McCulloh of the United States Geological Survey and deposited into the Smithsonian Institution as specimen number 62383.

The isolated wing fragment, LACM 533, from which the species was described was found in 1957 by Wilma Webster in the Calico Mountains, San Bernardino County, California.

Cambay amber dates to between fifty and fifty-two million years old, placing it in the Early to Mid Ypresian age of the Eocene, and was preserved in a brackish shore environment.

[1] The fossils were first studied by paleoentomologists Michael S. Engel and David Grimaldi.and their 2011 type description of the species was published in the journal ZooKeys.

[1] The specific epithet krishnai is in honor of Kumar Krishna, considered a world authority on fossil and living termites.

P. krishnai also shows a distinct more basal placement of the Medial vein fork then seen in the other species with the wing tip preserved.