Vandalernes invasion i det 5. århundrede medførte nedgang for byen, og udgravningerne viser, at byen blev ødelagt mellem år 425 og år 455. I 902 erobrede araberne Mallorca og lagde det ind under emiratet i Cordoba. Alcudia ("Højen") var det navn, som araberne gav området.

Efter Mallorcas indlemmelse under Aragonien i 1229 opdelte kong Jaime I øen i 8 dele, hvor han selv beholdt de 4 dele og delte de øvrige 4 dele - herunder Alcudia området - ud til fremtrædende riddere, som havde bistået i erobringskampen. Senere beordrede Jaime II bygning af en landsby ved siden af et arabisk landbrug. Han købte selv et hus på stedet og igangsatte bygning af den gamle bydel med en landsbykirke og en kirkegård. Byen antog ikke uventet Sankt Jakob (Jakob=Jaime) som sin skytshelgen. Andre vigtige bygninger fra den tid er hospitalet og Santa Anna kirken.

Fra 1298-1362 blev der bygget en mur omkring Alcudia, ikke alene for at beskytte byen men hele den nordlige region af øen. I begyndelsen af 1500-tallet, da de fattige gjorde oprør mod herremændene, måtte de adelige søge tilflugt indenfor murene, indtil kejser Karl V havde nedkæmpet oprøret. Oprørslederen Joanot Colom blev tortureret og halshugget, hvorefter hans hoved blev hængt op på en stage på Santa Margalida kirken i Palma. Byen Alcudia's trofasthed mod kronen resulterede i, at den i 1523 fik tildelt forskellige privilegier såsom skattefritagelse og fik status af "trofast by".

Murene var i gennemsnit 6 meter tykke og forstærket med 26 små tårne. Der var oprindelig 3 byporte, som selvfølgelig blev lukket ved mørkets frembrud og åbnet igen den følgende morgen. I dag er kun 2 af de oprindelige byporte tilbage, den østlige Xara og den vestlige Sant Sebastia. I 1500-tallet blev muren forstærket med 4 bastioner, hvor de 3 stadig er intakte.

Efterhånden som artilleri blev kraftigere, var de gamle mure ikke længere tilstrækkelige til at forsvare byen, og fra 1598-1660 blev der bygget en ydre ring om byen. Den ydre mur havde 4 byporte og 8 tårne. I 1893, da frygten for ydre fjender var væk, begyndte man at nedbryde den ydre bymur. I dag er kun bastionen Sant Ferran intakt. Denne står i nærheden af byens tyrefægterarena.

Årene efter opstanden blev meget vanskelige for øen og Alcudia. Dens beliggenhed nær kysten var handelsmæssigt en fordel - men også en ulempe, for de frygtede sørøvere slog til gang på gang. Mange følte sig tvunget til at forlade Alcudia. Omkring 1800 forsøgte man at skabe lidt fremgang i området ved et udbygge havnen og få 'genbefolket' byen. Men rigtig gang kom der først i området, da man midt i 1950'erne bygge et elektricitetsværk ved havnen, som i dag forsyner hele øen. Smukt er det dog ikke.

Turister begyndte at invadere Alcudia i begyndelsen af det 20. århundrede, men det store boom kom først i 1970'erne. Det store marskområde Albufera blev drænet og store hotelkomplekser skød op. I 1980'erne eksploderede turismen, og i dag er Alducia området helt og holdent afhængig heraf. En lokal anslog, at 80-85% af indtægterne stammede fra turisme. Byen har ca. 10.000 fastboende indbyggere, men mere end 30.000 hotelsenge.