Molinos fue donado juntamente con Monroyo y Ejulve por Pedro II de Aragón, en 1209, a la Orden de Calatrava cuya encomienda mayor radicaba en Alcañiz. La iglesia parroquial de Molinos se construyó lógicamente bajo el mecenazgo de la orden como podemos observar en las claves de las bóvedas de la iglesia decoradas con la Cruz Calatrava. El tipo de iglesia de una nave, con contrafuertes en el exterior y ábside poligonal, es fácilmente adscribible al estilo gótico levantino, tan extendido a lo largo de la Corona de Aragón.
Se abre a dos plazas, la Mayor y la del Ayuntamiento, contribuyendo a configurar un espacio en el que los edificios públicos y religiosos se organizan jerárquicamente.
El templo consta de nave única de tres tramos con capillas abiertas en el lado del Evangelio y unidas a modo de nave lateral, mientras que en el lado de la Epístola presenta una sola capilla y el acceso a la sacristía junto a la cabecera.
La cabecera, orientada hacia el este es poligonal y se cubre con bóveda nervada, que en la nave se convierte en bóveda de crucería sencilla con claves talladas.
El interior es muy sobrio y equilibrado. La iluminación penetra a través de óculos perforados en cada uno de los tramos del muro meridional. A los pies de la nave hay un coro alto, cerrado en su frente por un pretil de piedra sobre arco escarzano.
Las portadas, situadas en los muros oeste (a los pies del edificio) y sur (lado de la epístola) son, como el resto de la iglesia, de estilo gótico.
La portada sur está se abre en el tramo central de la nave. El vano de acceso se encuentra bajo un arco apuntado, enmarcado por arquivoltas decoradas con motivos escultóricos, rematadas por un arco conopial y apeadas sobre columnillas de fustes muy estilizados. En la parte superior de la portada se disponen tres bandas horizontales superpuestas con arquerías ciegas y tracerías góticas en relieve.
La portada del oeste presenta importantes similitudes con la anterior. Se abre en un arco apuntado enmarcado por arquivoltas, que tienen como remate un arco conopial decorado. El trasdós está decorado con tracerías y enmarcado por pináculos adosados que cierran la composición.
La fábrica es de sillar y presenta potentes contrafuertes, además de un pretil en la parte superior, tal vez defensivo, ya que esta iglesia perteneció a la orden de Calatrava.
La torre es una construcción exenta, sitúa a unos metros de la iglesia, sobre una colina cercana. Tiene cuatro pisos de altura, los dos primeros de planta cuadrada y realizados en mampostería con sillar en las esquinas, mientras que los dos superiores son de planta ochavada y están realizados en ladrillo.
Otras iglesias también pertenecientes al gótico levantino en la Comarca del Maestrazgo son: Iglesia de San Miguel en Castellote e Iglesia de San Miguel en Cantavieja.
