A l’època de dominació àrab, el territori que actualment ocupa el municipi d’Algaida estava inserit en una unitat administrativa major que s’anomenava Juz’ de Muntuy que, se suposa, ocupava els actuals termes municipals d’Algaida, Campos, Llucmajor, Montuïri, Santanyí i ses Salines. La població musulmana no estava reunida en grans nuclis de població tal com els coneixem ara, sinó que s’agrupava al voltant de punts d’explotació agrícola —alqueries i rafals— situats als llocs de terres més fèrtils o propers a punts d’aigua i que, posteriorment, donaren lloc als pobles de Randa, Pina i Algaida. Els àrabs foren els constructors de tota una sèrie d’enginys hidràulics per a la captació d’aigua. En són una bona mostra els diversos pous, sínies i qanawats. Entre aquests darrers cal destacar el de son Reus de Randa que, amb 299,8 m de recorregut subterrani, és el més llarg de Mallorca.

Com a conseqüència de la conquesta catalana de 1229, les terres del municipi d’Algaida varen correspondre al rei i foren repartides entre els homes de Jaume I. Algunes zones concretes foren donades a l’infant Pere de Portugal —part de l’alqueria de Punxuat— i a l’orde del Temple —puigs de Randa i l’alqueria de Rufassa—. Immediatament després de la conquesta els nous pobladors cristians edificaren l’església de Castellitx —surt citada per primer cop l’any 1249— esdevenint, així, un dels primers temples de repoblació. Durant l’edat mitjana Castellitx degué esdevenir un indret de notable transcendència: els antics camins que comunicaven les comarques del Pla i Llevant de Mallorca hi feien via i fins al segle XV donà nom al terme administratiu que actualment coneixem com Algaida.

A finals del segle XIII la població, que fins en aquell moment havia romàs dispersa per tota la contrada, experimentà la tendència a agrupar-se en nuclis d’explotació agrícola. L’alqueria d’Algaida esdevingué la principal concentració d’habitants, i Pina i Randa, entre d’altres, en secundaris. Al segle XIV el nucli algaidí es consolidà definitivament malgrat que Castellitx continuà essent el centre religiós fins que, aproximadament l’any 1410, es produí un canvi de titularitat a favor de l’església d’Algaida.

A finals del segle XVI la població del municipi era de 1.500 habitants. En aquests temps patí tota una època de daltabaixos que assolaren tota l’illa de Mallorca: epidèmies de pesta, períodes de fam i cicles de sequera. Malgrat aquestes vicissituds la població anà augmentant al llarg del segle XVII i del XVIII fins situar-se, ja al XX, als 4.000 habitants, xifra que representa la màxima població del terme. Al llarg d’aquests segles es bastí, en successives etapes, l’església parroquial d’Algaida.