Het valt moeilijk aan te geven wanneer precies en om welke reden Paestum werd gesticht. De Griekse schrijver Strabo vermeldt dat Grieken uit Sybaris een versterkte nederzetting stichtten in de buurt van de monding van de rivier Silaros (nu de Sele, ca. 10 km noordwaarts van Paestum) en dat zij hun hegemonie tot in de omliggende gebieden hadden weten uit te breiden. Een andere antieke bron vermeldt dat aan het begin van de 7e eeuw v.Chr. Dorische inwoners van Sybaris, nadat zij door hun Achaeïsche stadsgenoten verdreven waren, hier een eigen kolonie stichtten. Deze stad werd Poseidonia genoemd, naar de zeegod Poseidon, omdat de zee, die zij onder de bescherming van deze god bevaren hadden, de bron van hun voorspoed werd.
De kolonie dankte haar ontwikkeling aan een gunstige geografische ligging op een kruispunt van handelswegen tussen de Griekse en de Italische invloedssfeer. In de loop van de 7e eeuw was de invloed van de Etrusken in de omgeving afgenomen, en kreeg Poseidonia de kans om haar hegemonie te vestigen, ten nadele van de oorspronkelijke bewoners, de Italische stam der Lucaniërs. De stad bereikte haar economische, politieke en culturele hoogtepunt, nadat de moederstad Sybaris verwoest werd door concurrent Crotona. Het is aannemelijk dat een groot gedeelte van de verdreven Sybarieten in Poseidonia niet alleen goed onthaald werden, maar met hun bezittingen en hun ervaring de economie van hun vroegere kolonie ook nieuwe impulsen hebben gegeven. Uit deze bloeiperiode dateren drie grote, goed bewaarde tempels en talrijke andere kunstwerken.

Rond 400 v.Chr. waren de oorlogszuchtige en ondernemende Lucaniërs, een Italisch volk dat oorspronkelijk uit de centrale Apennijnen kwam, in dergelijke mate geïnfiltreerd in het stedelijke leven van Poseidonia, dat zij de stad geleidelijk in handen konden nemen. Toch had hun overheersing in de 4e eeuw v.Chr. geen nadelige invloed op het economische en culturele leven van de kolonie. Integendeel, de rijpere Griekse kunst beïnvloedde veeleer de simpele Lucanische kunstproducten, zoals in het plaatselijke museum duidelijk geïllustreerd wordt.

Rond het einde van de 4e eeuw raakte Poseidonia betrokken in zware oorlogen tussen de Grieken in Magna Graecia en de Italische volkeren die nieuwe gebieden aan zee wilden veroveren. Terwijl de Grieken de inval van de Italische volkeren probeerden te stuiten en daartoe de hulp van het koninkrijk Epirus hadden ingeroepen, wisten de Romeinen hun invloed te vergroten en onder meer koning Pyrrhus van Epirus te dwingen het land te verlaten.
In 273 v.Chr. bezetten de Romeinen Poseidonia en veranderden zij de naam in Paestum. De stad werd gedeeltelijk geromaniseerd, en de inwoners kregen het statuut van socii. Zij werden voor Rome trouwe bondgenoten, die de Romeinen meermaals op belangrijke momenten te hulp kwamen, onder meer in de moeilijke oorlog tegen Hannibal. Dankzij deze trouw behield de stad tot de regering van keizer Tiberius onder meer het recht om haar eigen munt te slaan. Gedurende de Romeinse periode werden nieuwe openbare gebouwen neergezet, een forum werd aangelegd, en zo kreeg Paestum het definitieve uitzicht dat bij de opgravingen aan het licht kwam. De stad bleef ononderbroken in gebruik tijdens de Romeinse keizerperiode, maar begon vanaf de 4e eeuw in belang af te nemen, als gevolg van meerdere oorzaken. Strabo schreef dat het in zijn tijd ongezond leven was in Paestum, door de moerasvorming in de omgeving. De ontbossing van de naburige bergen (voor economische en militaire doeleinden) veranderde immers het stroomgebied van de rivieren drastisch en werkte moerasvorming in de hand, zodat de malaria de gezondheid van de bewoners begon te ondermijnen. Bovendien had de aanleg van nieuwe wegen, die Rome directer via de Adriatische Zee met het Oosten verbonden, Paestum als verkeersknooppunt minder aantrekkelijk gemaakt.

De stad kromp ineen tot een schamel dorpje rond de zogenaamde Ceres-tempel, die later in een christelijke kerk werd omgedoopt, en werd zelf helemaal verlaten tijdens de Middeleeuwen, nadat de inwoners in de 9e eeuw de naburige bergen introkken, op de vlucht voor de malaria en voor de Saraceense piraten. Na haar teloorgang werd zij nog enkel aangehaald door historici en dichters, die dan vooral verwezen naar haar prachtige rozen (bifera rosaria Paesti, die tweemaal per jaar bloeien).

Pas in 1752 traden de ruïnes pas opnieuw in de belangstelling, na de herontdekking van de Romeinse steden Pompeï en Herculaneum, toen er in opdracht van koning Karel (IV) van Bourbon een weg (de huidige rijksweg nr. 18) naar het zuiden werd aangelegd.

Het huidige Paestum is een populaire toeristenplaats. De belangrijkste attracties vandaag de dag zijn de drie goed bewaard gebleven tempels in Dorische stijl, die dateren uit de eerste helft van de 6e eeuw v.Chr.. Hiervan zijn er twee gewijd aan de Griekse godin Hera en de derde aan Athena.