Mesto založil macedónsky kráľArchelaos I. v roku 399 pred Kr. ako nové hlavné mesto. Dovtedy bolo hlavné mestoAigai. Pella bola postavená na štýl juhogréckych mestských štátov, stáli tu impozantné stavby, kráľovský palác a agora. Pôsobili tu mnohí známi grécki umelci. V 2. storočí pred Kr. mesto ovládliRimania a jeho význam v Rímskom impériu poklesol, neskôr sa z Pelly stalo iba menšie provinčné mesto, centrum Macedónie bolSolún. CisárAugustus do mesta umiestnil rímskych kolonistov, hlavne vojenských veteránov.
V 6. storočí po Kr. bola Pella zničenáSlovanmi, tí sa tu aj usadili a od tejto doby je to slovanské mesto, jedno z najjužnejších slovanských miest vGrécku.
Neskôr sa miestni Slovania hlásili k bulharskej národnosti. Počas tureckej doby bolo mesto známe akoПостал (Postal, Apoštol).V roku 1900 tu žilo 720Bulharov. V roku 1912 bola celá Macedónia oslobodená Gréckom, mesto bolo známe pod gréckym menomΆγιοι Απόστολοι (Ajii Apostoli, Svätí Apoštoli).
Miestni Bulhari odišli doBulharska počas Grécko-bulharskej výmeny obyvateľov a do mesta prišli etnickíGréci zBulharska. Po Grécko-tureckej výmene obyvateľov (1923) sa v meste usadilo grécke obyvateľstvo ztureckej Trácie, konkrétne z dedínMega Revma (dnesArnavutköy, neďalekoIstanbulu) aNeo Chorio (dnesGenikioi pri mesteGelibolu). Mesto tak ostalo čisto grécke. V roku 1936 bolo mestu vrátené antické menoPella. Usadili sa tu aj grécki pastieri,Sarakacani zFloriny.