Al igual que la mayoría de las poblaciones que pertenecieron a la Orden de Santiago, no tiene historia conocida hasta el siglo XV, donde ya aparece como núcleo organizado y estructurado en todos sus aspectos.

Casi con toda seguridad su origen estaría en la construcción del puente, sobre el arroyo Palomillas, de la que tomaría el nombre de Palomas, y a su alrededor se iría articulando el núcleo poblacional, extendiéndose desde la calle corredera que era un cordel de la Mesta hasta sus aledaños -desde Logroño, se trasladaban a Palomas-. Consta en los archivos que en el último cuarto de siglo XV se abordaron obras de reconstrucción y conservación en el puente por orden de los Reyes Católicos.

Fueron éstos los que hicieron a Hornachos cabeza de partido dentro de la jurisdicción del triorato de Llerena, quedando su demarcación compuesta por 14 aldeas en las cuales se incluye a Palomas, hasta mucho más tarde en 1618 no se alcanzó la categoría de Villa eximida, comprando los derechos a la corona.

De acuerdo con las estadísticas del padrón municipal de 1996 Palomas contaba con 700 habitantes y con una superficie de 40.5 kms 2 de un terreno ondulado y con varios cerros como La Horca o el Calvario.

A pesar de que hoy ha desaparecido, la Casa de la Encomienda existió hasta 1910. Con anterioridad dicha casa pasó a manos del imperio de la familia Quirós, que por entonces era la dueña de casi todo el término. Y para que el pueblo no olvidara el poderío de este linaje, mandaron esculpir en el Alta Mayor de la Iglesia Ntra Sra de Gracia, la inscripción siguiente: "Después de Dios, la Casa de Quirós".

En Palomas se desarrollan los acontecimientos narrados en la obra de Felipe Trigo "El médico rural".

IGLESIA NUESTRA SEÑORA DE GRACIA

Llama la atención que en un núcleo tan reducido de población se construyeran tan soberbia torre, que constituye uno de los más destacado ejemplos de realizaciones del estilo mudéjar de Extremadura, sigue el ejemplo de lo que se denomina torres-fachada.

Situada sobre la zona más alta de la población, domina desde su atalaya todo el entorno con su majestuosa presencia. Se trata de una construcción mudéjar originaria del siglo XV, realizada en mampostería y ladrillo, en la que sobresale una soberbia torre.

La planta de la iglesia es de una sola nave, con bóveda de cañón dispuesta en el siglo XVIII para sustituir la original de alfarje.  La torre, dispuesta en avance sobre los pies, centrada en el edificio, constituye acabado ejemplo del modelo de torre fachada. Está ejecutada por completo en ladrillo y costa de tres cuerpos.