El registro fósil de Rhineuridae se extiende casi hasta el Mesozoico, apareciendo el más antiguo rinéurido, Plesiorhineura tsentasai a inicios del Paleoceno.[6] Plesiorhineura solo es conocido a partir de una mandíbula parcial, pero comparte varios rasgos con los rinéuridos modernos. Los rinéuridos del Eoceno, como Spathorhynchus fossorium, son notablemente similares al actual Rhineura, lo que sugiere una evolución muy conservadora en la familia. A diferencia de los Amphisbaenidae, los cuales incluyen a formas con cabezas redondeada, y con hocicos en forma de quilla y pala, los rinéuridos son exclusivamente de la variedad con hocicos de pala. Los rinéuridos fósiles son conocidos exclusivamente de Norteamérica. pero dado que tuvo una distribución mayor en el pasado (estados de Colorado, Wyoming, Dakota del Sur, Montana y Oregón)[7][8] probablemente refleja el hecho de que el clima era mucho más cálido en el pasado. La radiación evolutiva de los rinéuridos en Norteamérica ocurrió cuando la mayor parte del continente era húmedo y subtropical. Los rinéuridos persistieron tras la significativa transición climática por la época del límite entre el Eoceno al Oligoceno en la cual la mayor parte de Norteamérica se volvió semiárida y cubierta por sabanas. El declive de los rinéuridos comenzó con un abrupto período de enfriamiento conocido como la disrupción del Mioceno medio. El rango de distribución de los rinéuridos se redujo hacia al sur a medida que las temperaturas globales continuaron cayendo, dejando a R. floridana aislado en la Florida como el último representante vivo de su grupo.[9]
En 2007, el paleontólogo Daniel Hembree revisó a todos los anfisbenios fósiles norteamericanos y encontró que todas las especies pertenecían a Rhineuridae. Él también mostró que muchos rinéuridos extintos no pueden ser clasificados como sus propias especies y son en cambio sinónimos de especies anteriormente nombradas, reduciendo el número de especies válidas de veintidós a nueve. Por ejemplo, Jepsibaena minor, Rhineura amblyceps, R. attenuatus R. minutus y R. wilsoni son todos sinónimos de Protorhineura hatchetii, dejando a R. floridana como la única especie de Rhineura. Desde el siglo XIX, los paleontólogos habían estado nombrando especies nuevas de anfisbenios norteamericanos basándose únicamente en especímenes fragmentarios que con frecuencia preservaban muy pocas características como para justificar su estatus como especies diferentes. Al sinonimizar a muchas de estas especies, Hembree mostró que la diversidad de rinéuridos de América del Norte era mucho más baja de lo que se había pensado.[5]
