Comienza a competir en la Regional Preferente Andaluza consiguiendo en una sola temporada el ascenso a la Tercera División. El debut en la nueva categoría se produce en 1984 y tras dos temporadas ocupando los primeros puestos de la clasificación. En el año 1986 logra el ascenso a la Segunda B. Tres temporadas consigue mantenerse en la nueva categoría: la primera salvado del descenso por una reestructuración, la segunda con ciertos apuros, y en la tercera (1988/89) desciende finalmente de nuevo a la Tercera División y con graves problemas económicos que casi hacen desaparecer a la entidad.

Finalmente el equipo sale a competición, aunque debido a la falta de planificación queda clasificado en la mitad de la tabla. La siguiente campaña (1990/91) comienza con un proyecto ambicioso en busca del ascenso, pero la grave crisis económica provoca el cambio, a mitad de temporada, de gran parte de la plantilla, haciendo que el equipo quede clasificado peor todavía que el año anterior (13º). En el verano de 1991 comienza una etapa de estabilidad en el club lo que posibilita que, en la tercera temporada consecutiva en la categoría, el equipo se quede a las puertas de luchar por el ascenso (5º). La siguiente temporada (1992/93) sí consigue meterse (3º) pero sin mucho éxito. Finalmente el objetivo del ascenso a la Segunda B se alcanza en 1994 con una plantilla formada al 95% por futbolistas almerienses, demostrando además una gran superioridad durante todo el campeonato (1º).

Una vez recuperada la categoría, se abre un período de siete temporadas consecutivas en la división. En la primera de ellas (1994/95) se mantiene el clima de estabilidad previo y consecuencia de ello se acaba la campaña en la mitad baja de la clasificación pero sin pasar muchos apuros a lo largo del campeonato (15º). La siguiente temporada termina en la zona media de la clasificación, intentanto sin éxito hacer un equipo competitivo para optar a los puestos altos (9º). La temporada 1996/1997 supone un revés a la trayectoria del equipo pues, tras la mala campaña, se consigue lograr la permanencia en la categoría por medio de la eliminatoria de descenso a la Tercera División (16º). La cuarta temporada consecutiva en la categoría no tuvo el sufrimiento final de la anterior, pero tampoco fue buena, aunque se consigue el objetivo de la permanencia (14º). La quinta (1998/99) fue sin embargo la temporada de la consecución, por vez primera en la historia del club, de la disputa de la fase de ascenso a la Segunda División (4º), pero no se logró el objetivo del ascenso aunque se peleó casi hasta el final. En la temporada 1999/2000 el club parte como uno de los favoritos para repetir los logros de la campaña anterior, pero al final no se consigue al quedar quinto y a un solo punto del cuarto clasificado, por lo que queda fuera de la liguilla de ascenso. La gran anécdota de la temporada fue sin duda la eliminatoria de dieciseisavos de final de la Copa del Rey disputada frente al F.C. Barcelona, jugándose los dos partidos más importantes de la historia del club (0-0 en la ida, en Almería, y 2-0 en la vuelta en Barcelona -goles conseguidos en los últimos 5 minutos de partido-), además de un importante respiro económico.

La séptima y última temporada consecutiva tuvo un final precipitado, pues en 2000, a falta de dos jornadas para el final de la primera vuelta, se consumó la retirada de la competición y el descenso automático a la Tercera División, anulándose todos sus resultados obtenidos hasta ese momento. Esto propició la marcha de los jugadores de la plantilla a distintos equipos de la categoría. La temporada siguiente (2001/2002) le correspondía jugar en la Tercera División, pero finalmente no se inscribe en la competición. De hacerlo en la siguiente, debía de ser en la última categoría provincial, lo que se intenta en 2002, pero finalmente el proyecto no sale adelante.

En el año 2003 se produce por fin el regreso del club a la competición, en la Primera Provincial de Almería, categoría en la que se mantiene durante cuatro campañas consecutivas. La primera temporada (2003/2004) empieza con el objetivo del ascenso de categoría, que finalmente no se consigue (a pesar de la reestructuración del fútbol andaluz), suponiendo un golpe moral a la entidad. La siguiente temporada se vuelve a intentar el salto de categoría, para lo cual se producen algunos cambios en la entidad, pero una serie de malos resultados puntuales hacen que al final de la liga no se pueda optar a los puestos de ascenso. La tercera temporada en la categoría supone un gran paso atrás del club, pues al final de la liga queda clasificado en la mitad baja de la clasificación, sin haberse acercado nunca a los puestos de arriba. La cuarta temporada consecutiva, la 2006/2007, se disputó la liga dividida en dos grupos de los cuales, al finalizar la competición, diez equipos jugarían una fase de ascenso, fase a la que el equipo no logra clasificarse por un solo punto, tras una campaña aceptable aunque con algunos momentos bajos que propiciaron la clasificación final. En la temporada 2007/2008 le correspondía participar de nuevo en la Primera Provincial de Almería, pero finalmente el club no se inscribe en la competición. Comienza así un nuevo periodo de inactividad para la entidad, que se prolonga hasta la temporada 2011/2012, en la que se inician contactos para reiniciar la actividad deportiva que finalmente no fructifican.

El año 2012 marca la nueva vuelta a la competición del club. Participa la temporada 2012/2013 en la categoría Regional Preferente, en esos momentos última categoría en la provincia de Almería, dividida en dos grupos, quedando adscrito el equipo en el grupo I.
Estadio

El Club Polideportivo Almería juega en el Estadio de la Juventud Emilio Campra. Cuenta con pistas de atletismo y césped artificial, y su aforo es de 2500 espectadores. Está situado en el barrio almeriense del Zapillo.
Aunque históricamente ha jugado la gran mayoría de sus partidos en el Estadio Juan Rojas (antes Franco Navarro, inaugurado en 1976). Su aforo es de 13648 espectadores (5468 sentados y 8000 de pie). Está situado en el barrio almeriense de Torrecárdenas.

Otros recintos utilizados fueron el campo federativo Matías Pérez, en el barrio almeriense de La Cañada de San Urbano y el Jerónimo Rodríguez, en la localidad almeriense de Benahadux.