En tiempos d'Al-Ándalus Navas de San Juan sería una alquería o pequeña población integrada dientro del distritu alministrativu de Sant Astiban o pueblu de comerciantes. Los musulmanes construyeron un castiellu, del que tan solo nos llegaron delles fotografíes, y que darréu foi reformáu polos cristianos. Nel so términu hai restos d'otres estructures fortificaes como'l castiellu de Ero y la torre del homenaxe alredor de la cual edificóse l'actual Santuariu de Santa María de la Estrella.