Præstø blev omtalt første gang i et brev fra 1321 og fik købstadsprivilegium i 1403. Byens opståen hænger muligvis sammen med nordtyske byers stigende efterspørgsel efter dansk korn fra og med 1200-tallet. Præstø var også en af de byer, der nød godt af de skånske sildemarkeder i senmiddelalderen. I 1470 skænkede Christian 1. kirken til antoniterne, som opførte ordenens eneste danske kloster i tilknytning til kirken. Klosteret blev nedrevet 1562‑63.
1600- og 1700-tallet var præget af katastrofer: stormflod (1625), krigshandlinger (1657‑60), pest (1711) og mange bybrande. Ved brandene i hhv. 1750 og 1757, der ramte hver sin bydel, gik næsten alle de ca. 70 ejendomme op i luer. I 1787 var der 402 indbyggere i Præstø. Det begyndte først at gå fremad efter år 1800, da stigende landbrugsproduktion efterudskiftningen øgede oplandets efterspørgsel efter købstadens ydelser. Den begyndende optimisme kom til udtryk ved etablering af dæmninger mod vest og syd i hhv. 1804‑05 og 1819 som erstatning for de hidtidige broer, og efter opfyldning ved Vesterbro begyndte man i ca. 1840 at bebygge dette område. I 1828 fik byen også en havn; indtil da måtte omladning til og fra skibene foregå i åbent farvand.
Præstø, der i 1845 kun havde 852 indbyggere, voksede gennem hele 1800-tallet, og i 1901 havde byen 1.497 beboere. I 1873 erhvervede kommunen Nysø Huse, og i 1915 købte man præsteembedets jorder syd for Tubæk, som blev til kvarteret Præstemarken. Næstved- Præstø-jernbanen, der blev anlagt i år 1900 og forlænget til Mern i 1913, styrkede Præstøs evne til at tiltrække turister; allerede i 1903 havde byen 16 hoteller og gæstgiverier.
Fra 1901 til 1960 lå Præstøs befolkningstal nogenlunde stabilt, men kommunesammenlægningerne i hhv. 1966 og 1970 gav mulighed for en udvidelse af bygningsmassen mod syd og øst, og i 1970 var byens indbyggertal vokset til 2.789. Erhvervslivet var gennem 1900-tallet præget af et ret stort antal handels-, industri- og håndværksvirksomheder, men de havde for det meste et beskedent omfang. I 1960’erne havde byen hele 12 købmandsforretninger.
Præstø fortsatte sin vækst mellem 1970 og 2006, hvor byen var administrativt center for kommunen med samme navn, og i 2006 havde byen 3.863 indbyggere. I denne periode fik den bl.a. en række sociale og kulturelle institutioner, en idrætshal (1976) og et søsportscenter (1976). Til gengæld ophørte byen med at have toldkammer (1970) og politi (1972).
