Paleontologists just recently opened their eyes to the wealth of fossil documents relevant to plant - arthropod interaction and are busy now accumulating raw data. Perhaps the richest regional collection of interaction traces came from the mid-Cretaceous deposits of the Negev Desert, Israel, encompassing the time interval of the rise and basal radiation of angiosperms - the flowering plants. The arthropods (insects and mites) inserting their eggs in the leaves and making leaf mines and galls were discovering new possibilities for endophytic life that the flowering plants provided. Their morphological disparity suggests a diversification race, in which the angiosperms failed to override their leaf parasites. Only a small fraction of insect diversity is represented by body fossils that belong to one extinct and nine extant families of beetles and cockroaches mostly. Because similar structures are produced on leaves by parasitic arthropods of different systematic alliances, a purely morphological classification is worked out for the trace fossils, with but tentative assignments to natural taxa, referring to distinct types of parasitic behavior. It is the Evolution of behavior that is documented by the trace fossils. The body fossils and parasitic traces represent morphologies and behavioral traits fairly advanced for their geological age. The expression, abundance, co-occurrence, and host specialization of parasitic structures, as well as the marks of predation on mines and galls betray regulatory mechanisms of plant - arthropod interaction, analyzed in the broad context of ecosystem evolution, paleogeography and climate change.