Arkeologisten löytöjen perusteella alue on ollut asuttu paleoliittisella ja neoliittisella kaudella. Poseidonian kaupunki perustettiin etelämpänä sijainneen Sybariin kreikkalaiskaupungin siirtokuntana antiikin Kreikan arkaaisella kaudella 600-luvun eaa. puolessa välissä. Samalla seudun varhaisempi väestö joutui muuttamaan sisämaahan. Siirtokunnan perustajina saattoivat olla Sybariin troizenilainen väestö, jonka akhaialaiset olivat karkottaneet kaupungista. Strabonin mukaan kaupunki perustettiin ensin lähemmäksi merta, mutta siirrettiin sitten hieman kauemmaksi rannikosta.[1][2][3] Kaupungin kansalaisista käytettiin etnonyymejä Poseidōniatēs (Ποσειδωνιάτης), myöhemmin Paistanos (Παιστανός) ja latinaksi Paestanus.[2]

 

Poseidonian lyömä raha, n 530–500 eaa. Kummankin puolen kuvituksessa Poseidon kolmikärkineen.

Poseidoniasta tuli nopeasti kukoistava sen ympäristön hedelmällisen maaperän ja kaupankäynnin ansiosta. Kaupungin varhaisesta historiasta tiedetään kuitenkin vain vähän, jopa vähemmän kuin Suur-Kreikan muiden kaupunkien alkuvaiheista. Arkeologisista jäänteistä tiedetään, että kaupunki laajeni, ja sinne rakennettiin suuria kreikkalaisia temppeleitä. Sieltä on löytynyt myös kolikoita ja metallisia pienoispatsaita. Löydöt yhdessä osoittavat kaupungin menestyneen.[1][2]

Ensimmäiset kirjalliset maininnat Poseidoniasta ovat vasta 400-luvun lopulta eaa. Tuolloin Herodotos mainitsee kaupungin tavalla, joka osoittaa sen olleen merkittävä viimeistään naapurikaupunki Elean (Velia) perustamisen aikaan noin 540 eaa. Sybariin tuhon vuonna 510 eaa. jälkeen kaupunkiin muutti mahdollisesti uutta väestöä, joskin Herodotos mainitsee jäljelle jääneiden sybarislaisten muuttaneen vain Laokseen ja Skidrokseen.[1][2][4]

 

Paestumin arkeologista aluetta.

Koska Poseidonia sijaitsi suhteellisen pohjoisessa, se oli kreikkalaiskaupungeista ensimmäisiä, jotka kärsivät paikallisen ei-kreikkalaisen heimon lukaanien noususta alueella ja joutui lopulta näiden vallan alle. Tämä ajoitetaan noin vuosiin 400–390 eaa. Antiikin lähteiden mukaan kreikkalaisia ei tuolloin karkotettu kaupungista, vaan heidän tuli pelkästään alistua barbaarien valtaan ja ottaa kaupunkiin näiden varuskunta. Seurauksena kaupunki säilytti ainakin osittain kreikkalaisen luonteensa jonkin aikaa. Lukaanit antoivat kaupungille uuden nimen Paiston tai Paistos.[2][5]

Epeiroksen kuningas Aleksanteri I, joka taisteli Suur-Kreikassa barbaareja vastaan, vapautti kaupungin vuonna 330 eaa. Se vaikuttaa kuitenkin päätyneen takaisin barbaarien käsiin jo vuoteen 326 eaa. tultaessa.[1][2][6]

 

Kaupunginmuurin itäportti eli nk. Porta della Sirena.

Roomalaiset valtasivat kaupungin muun Lucanian ohella. Eteläisessä Italiassa Roomaa vastaan sotineen Epeiroksen kuninkaan Pyrrhoksen vetäydyttyä alueelta vuonna 273 eaa. roomalaiset tekivät kaupungista roomalaisen kolonian. Viimeistään tässä yhteydessä nimi vaihdettiin (tai muuntui) muotoon Paestum.[1][2]

Kaupungin ajasta roomalaisena koloniana tiedetään jälleen suhteellisen vähän. Hannibalin vallatessa Italiaa toisen puunilaissodan aikaan 218–202 eaa. Paestum pysyi uskollisena Roomalle ja tarjosi joukkoja ja laivoja sen käyttöön sodassa. Kaupunki mainitaan merkittävänä vielä Rooman tasavallan loppupuolella ensimmäisellä vuosisadalla eaa. Vuoden 90 eaa. Lex Julian myötä Paestumista tuli tavallinen roomalaiskaupunki.[1][2]

Strabonin mukaan Sele-joen liettyminen ensimmäisellä vuosisadalla jaa. muutti paikan epäterveelliseksi malarian leviämisen vuoksi. Tämän seurauksena Paestum alkoi mitä ilmeisimmin taantua. Kaupunki vaikuttaa kuitenkin säilyneen olemassa läpi Rooman keisarikauden.[1][2] Paestum tunnettiin muun muassa ruusuistaan, jotka kukkivat kahdesti vuodessa, keväällä ja syksyllä, ja joiden tuoksua runoilijat ylistivät.[2][7]

400-luvulla jaa. Paestumista tuli piispanistuin. Keskiajan alkupuolella kaupunki muodostui vain pienestä asutuksesta, joka oli keskittynyt kirkoksi muutetun pohjoisimman temppelin eli Athenen temppelin ympärille. Kaupunki hylättiin saraseenien hyökkäysten seurauksena noin 800-luvulla, ja piispanistuin siirrettiin naapurikaupunki Capaccioon ylemmäksi sisämaahan.[1][2]

Ajan kuluessa kaupungin paikka soistui ja metsittyi, ja se säilyi asumattomana hyvin pitkään. Pystyssä olleet temppelit säilyivät ainakin osittain näkyvissä, ja tunnettiin todennäköisesti lähiseudullaan, mutta ei laajemmin Euroopassa. Rauniot ”löytyivät” ja tulivat tunnetuksi vasta 1700-luvulla, toisin sanoen samoihin aikoihin yhdessä Pompejin ja Herculaneumin kanssa, kun oppineet matkailijat kuvasivat niitä teoksissaan. Niistä tuli uusklassismin aikana nopeasti hyvin kuuluisat ja varhainen turistinähtävyys.[1][2]

Hieman myöhemmin alkoivat alueen arkeologiset kaivaukset. Niitä suoritettiin laajassa mittakaavassa erityisesti 1920- ja 1930-luvuilla, jolloin lähelle rakennettiin myös rautatieasema turismin edistämiseksi. Toisen maailmansodan aikaan alue päätyi keskelle Salernon maihinnousua.[8]