Historia del colegio
En el BOJA DEL 15-05-89 se publica la resolución por la que se hace 
pública la adjudicación definitiva del contrato de obras para la construcción del C.P. La Paloma con 10 unidades.
El colegio «La Paloma» fue levantado por la Consejería de la Junta de Andalucía tras la cesión de los terrenos por parte del Ayuntamiento. El centro fue ubicado entre el recito ferial y el recién inaugurado parque La Paloma, muy próximo al centro urbano de Arroyo de la Miel.
Estaba previsto ser terminado en tres meses, según la concejala Alejandra Pérez Roca. En este plazo de tiempo la empresa sólo pudo levantar los cimientos y los 150 alumnos matric
ulados para el curso 89-90 en este centro tuvieron que ser distribuidos en distintas escuelas de la localidad como: «El Tomillar», «La Leala» o «El Poeta Salvador Rueda». Para ello se habilitaron las aulas necesarias y así los alumnos de «La Paloma» pudieron dar sus clases mientras se prolongaba la construcción de dicho centro.
a de un cable eléctrico.
Una vez terminada la primera fase, la escuela contaba con grandes deficiencias: no existían accesos adecuados al centro, ni pistas polideportivas ni espacios para recreo del alumnado. Tampoco había señalizaciones viales, ni existía presencia policial.
Esto, unido a otros hechos, como encontrar una tubería de alta presión en la inmediaciones del centro, motivo la protesta de profesores, padres y alumnos.
Se llevaron a cabo charlas con el alcalde. De estas se acordó la construcción de un muro de contención que desplazara el terreno y poder construir así, las pista y los patios necesarios para el alumnado.
Tras algunos problemas y retrasos en la construcción del colegio, se inaugura oficialmente en el curso 1990/91. 
Hasta el día 26 de Marzo de 1990, aproximadamente, no recibió el nombre de «La Paloma» y puesto que fue bautizado así , la calle en la que estaba situado el centro se denominó Avenida de la Paz.
En 1993 se re
alizan obras de reforma para 150 alumnos más (6 aulas y vivienda del conserje).
Poco a poco se ha completado su estructura actual, siendo la mas destacado la puesta en marcha del comedor escolar que comenzo a funcionar el 1 de Marzo de 1993.
El curso 2002/2003 se han completado los espacios de recreo del centro, contando actualmente con varias partes diferenciadas: el patio de infantil, dos pistas polideportivas y un porche cubierto para formación de las filas de entrada.
