Hay varias hipótesis sobre el origen del pueblo según su propio topónimo; a mediados del XIX Pascual Madoz apuntaba que vendría de Fraude, "por los muchos robos que se hacían en este sitio"; otra hipótesis es más verosímil: el nombre procedería de un grupo de monjes que se habrían establecido en el lugar. Según está segunda versión su origen se remontaría a la conquista castellana, a la creación de la abadía de Patronato Real en Alcalá la Real y a la carta de privilegio dada por Alfonso XI para poblar ésta.
El primer documento en el que se lo menciona está fechado el 7 de noviembre de 1463, con el nombre de Navas de Frailes; se señala como el lugar en el que el Condestable Lucas de Iranzo preparó su fallido asalto al castillo de Moclín, con 900 soldados a caballo, 800 ballesteros y 1.500 lanceros. Tras la conquista de Granada y la desaparición del peligro de ataques musulmanes, la población debió crecer y consolidarse.
Durante la Edad Moderna está población estuvo ligada a la villa de Alcalá la Real en calidad de aldea. En 1495 aparece como una aldea con 24 vecinos, entre 96 y 120 habitantes. Esta dependencia perduró hasta 1820, pero tampoco fue su emancipación definitiva, pues tres años más tarde la volvió a perder. La definitiva emancipación culminó en 1836, cuando el propio alcalde de Alcalá la Real dio posesión al primer alcalde de la villa de Frailes.
Ayuntamiento de Frailes

Este proyecto ha sido incentivado por la Consejería de Innovación, Ciencia y Empresa de la Junta de Andalucía. ORDEN 9 de mayo de 2006.