Aunque se tiene certeza, por los testimonios encontrados, de que estas tierras estuvieron pobladas desde épocas lejanas, sin embargo, la historia de Paymogo comienza a mediados del siglo XIII cuando fue conquistada por los Templarios, denominación que se le da a los caballeros de la Orden del Temple, que llegaron a la Península procedentes de Tierra Santa y, a mediados del siglo XII, comenzaron a extenderse por todo el territorio nacional. Como era normal por aquellos tiempos, los Templarios se dedicaban a la conquista de territorios, obteniendo gran poder en toda España, hasta que el rey Felipe IV, el Hermoso, decidió acabar con su prevalencia y, una vez derrotados, los llevó ante el Tribunal de la Inquisición. El Papa Clemente V protestó ante el monarca, iniciando la supresión de la Orden.
Se ha dicho que el nombre Paymogo se debe, según la leyenda, a un chamán que existió en la Sierra Morena onubense, del que se contaba tenía tales poderes que su fama trascendió a toda la comarca. Sus dominios terminaron llamándose País del Mago. El uso frecuente de esta denominación (PaiMago... Paymogo), terminó acortándose con el nombre de Paymogo. Se especuló que este mago era hermano de Guzmán el Bueno, que solía recolectar hierbas medicinales por los campos de aquellos lugares, tales como el poleo, cilantro, mastranzo, ruda... (Lasso, J. M. 1990).
Sin embargo, la versión más plausible sobre la toponimia de Paymogo la relaciona con la influencia portuguesa. Así, el nombre provendría de la composición de las palabras luso-latinas pagus, aldea en latín, y mogo, señal que delimita un terreno, como la castellana mojón. En consecuencia, el término Paymogo designaría un pueblo o aldea que se encuentra en la frontera.
Como curiosidad, a mediados del siglo XIX se adoptó oficialmente el cambio de la i por la y, pasando de Paimogo a Paymogo. Y otra curiosidad: al Norte de la ciudad de Lisboa, en Lourinhã, hay una praia de Paimogo y una fortaleza del mismo nombre levantada a partir de 1674, que conforma una línea de defensa del litoral luso contra la posible invasión castellana.
La primitiva población estuvo situada, según recoge la tradición, en un lugar cercano conocido con el nombre de Paymoguillo. Paymogo pasa de tener 51 vecinos en 1503 a tener 1615 habitantes a partir del año 1787. Este aumento de población se relaciona al parecer con el desarrollo económico. A mediados del siglo XVIII, la miel y la cera constituían una importante fuente de riqueza en el lugar.
Paymogo ha sido a lo largo del tiempo escenario de batallas fronterizas, ya que continuamente se veía afectado por las disputas territoriales con los vecinos portugueses. Coincidiendo con la Guerra de Sucesión, Paymogo junto con otras poblaciones de los alrededores, sufriría de nuevo las consecuencias de las invasiones portuguesas, llegando tales incursiones hasta San Juan del Puerto, entre 1704 y 1708. Ello provocó la construcción, en los lugares fronterizos, de diversos castillos y fortalezas para protegerse y defenderse de las invasiones del enemigo.
El pueblo cuenta con un castillo catalogado por la Junta de Andalucía como Bien de Interés Cultural, construido en el siglo XV y posteriormente reconstruido durante las guerras con Portugal, hacia la mitad del siglo XVII. Ha sido habilitado como conjunto Iglesia-Castillo, y fue declarado monumento Nacional el 22 de Abril de 1944.
Durante el siglo XIX comenzaron los primeros impulsos económicos del pueblo, con la explotación de las minas de pirita situadas en Romanera y Huerta Falsa del término municipal, aunque esta explotación duró poco tiempo por falta de capital, obligando a la comunidad a buscar nuevos horizontes comerciales para encauzar su economía.
Empezaron así a florecer la agricultura y la ganadería, predominando la cría y engorde del cerdo. La mayoría del término municipal está poblado de encinares, sus frutos (las bellotas) representan el mejor y más codiciado alimento para la producción del famoso jamón ibérico, que en la actualidad es uno de los manjares preferidos de la gastronomía española; reconocido internacionalmente. La producción de ganado ovino representa también otra fuente de riqueza de la tierra. Su ganadería ovina es de tipo recio y resistente a los cambios del clima, que no es muy frío en invierno, y de calor seco en verano; por lo que es también más llevadero.
