No se han encontrado yacimientos arqueológicos que indiquen una población permanentemente asentada en la zona.
No se han encontrado vestigios sobre el paso de los romanos por la población.
La primera noticia que se tiene sobre la población, y la que le da nombre es durante la época árabe. Alcudia significa en árabe “monte”. Dada su posición a 1.003 metros de altitud, dominando la hoya o valle de Tahal, y próximas a los montes Montahur (el actual cerro de Monteagud) y el monte Nimar.
La zona fue poblada por grupos tribales, al parecer de origen beréber, distribuyéndose en varios núcleos de población, como Alhabia, Benimedalá, Benalguacil alto y bajo, Benixaume y Jemecí (el Xemeçit de los documentos antiguos) .
Estos clanes, formados por personas que se consideraban descendientes de un antepasado común ya fuera éste real o mítico, usaban su propio nombre familiar para designar las aldeas que construían y levantaban junto a ellas pequeñas fortificaciones generalmente torres con las que marcaban y defendían el territorio del clan. La mayor de estas torres es la torre de Alhabia.
La actividad económica principal de la zona es la agricultura de secano (cereales, olivos, vides y almendros) y la ganadería. La caza también suponía un medio de subsistencia, dada la presencia de bosques de encinas, pinos de diversas especies entre ellos el longevo y majestuoso pino laricio, alcornoques y madroños. Las moreras también eran abundantes, de hecho en el escudo de la población aparecen 2 hojas de morera, elemento imprescindible para el desarrollo de la industria de la seda en la provincia.
Tras la conquista cristiana de la población y sobre todo tras la rebelión y posterior persecución de los moriscos en torno a 1570, la mayoría de las poblaciones fueron abandonadas por sus habitantes. En un intento de repoblar la zona, la Corona procedió a repartir los bienes dejados por los moriscos a ganaderos de la sierra de Segura (Jaén), campesinos de Castilla la Nueva y un extraño grupo de pastores vasco-franceses originarios del «vizcondado de Mavelón de Sola, reino de Francia». De hecho, Sola es hoy un apellido bastante frecuente en la comarca.
Para enfatizar el carácter católico de la población, se construye la iglesia de Nuestra Señora del Rosario, con detalles mudéjares típicos de la época.
Debido al carácter montañoso de la zona, durante los siglos XVII a XIX se lleva a cabo una intensiva labor de creación de balates y terrazas en las laderas de las montañas, con la intención de aumentar el área cultivable. Esto añadido a la necesidad de madera para la incipiente industria minera causó la progresiva desaparición de los bosques circundantes. Actualmente todavía quedan algunos restos de esos bosques, en lugares de difícil acceso.
Debido al aumento de la producción agraria, fueron necesarias la construcción de las infraestructuras necesarias, como la era grande, una de las más grandes en la provincia de Almería.
Con el fin de diferenciarse del resto de poblaciones denominadas “Alcudia” en España, se decidió añadir el topónimo “de Monteagud”.
Durante la guerra civil la población sufrió varios disturbios, que desencadenaron en el expolio de la iglesia.
Tras el declive de la industria minera, y ante la falta de oportunidades, los habitantes de Alcudia de Monteagud emigraron a otras zonas, con lo que no se consiguió frenar la progresiva despoblación.
En la actualidad cuenta con 135 habitantes. Su principal actividad económica es la agricultura y la ganadería, aunque dada su posición privilegiada y sus vistas sobre todo el valle de Tahal, es un lugar ideal para el turismo de interior y realizar rutas de senderismo.