The first known fossil heterostigmatic mite species, Protophenax kotejii gen. et sp. nov. (Acari: Acarophenacidae), is described and illustrated, based on the inclusion of three female specimens attached to a coccid male, Inka minuta Koteja 1989 (Homoptera: Coccinea: Inkidae), from Cretaceous taimyrian amber. The material is briefly discussed, with remarks on the fossil mites biology, morphology and systematics. A provisional key to the genera of Acarophenacidae is given. The conclusion that heterostigmatic mites had evolved before the Cretaceous period is supported.