Pollentia blev - formentlig nogenlunde samtidig med Palma - grundlagt af Romerne efter erobring af Mallorca i 123 BC. Det følgende år også Menorca lagt ind under romersk herredømme. Romerne blev ledet af konsul Quintus Caecilius Metellus. For denne bedrift og for at have ryddet op blandt de frygtede sørøvere i den del af Middelhavet fik Metellus 2 år senere sin velfortjente belønning i form af et triumftog gennem Rom op til Capitolium. Metellus - som fik tilnavnet Balearicus - 'flyttede' 3,000 utalienske veteraner fra det spanske fastland, hvor de én gang havde slået sig ned. Til hver af de 2 samfund, Pollentia (den mægtige) og Palma (Palmaria: sejrens palme), blev der knyttet militær garnisoner. Senere skal kejser Augustus have sendt endnu en gruppe kolonister til øen, ved hvilken lejlighed byerne fik status af romerske kolonier - vistnok som de første romerske kolonier udenfor den italienske halvø. Med det var Pollentia og ikke Palma, der var den førende by på øen.