Nysted menes at være opstået nogenlunde samtidig med Ålholm i midten af 1200-tallet, men det er uklart, om borgen skabte forudsætningen for byens opkomst eller omvendt. Under alle omstændigheder lå stedet godt for vareudveksling mellem Lolland og de nordtyske byer, der voksede frem i 1200-tallet. Nysted fik købstadsprivilegier i 1409.
Byen har aldrig haft handel eller håndværk af væsentligt omfang. Derimod kom landbrug og fiskeri til at spille en større rolle end i mange andre byer, og Nysted fik også en del sælfangst. I 1500-tallet eksisterede der et salpeterværk, og i 1700-tallet og indtil midten af 1800-tallet havde byen en stivelsesfabrik. Fra 1455 til 1845 blev Nysted ramt af ti brande, der i høj grad hæmmede byens udvikling. I 1787 havde Nysted 627 indbyggere.
Byen oplevede en markant vækst i 1800-tallet; i 1855 var der 1.227 indbyggere, i 1901 lå tallet på 1.411. Den stærkt stigende kornproduktion gavnede byen, som især i 1860’erne havde vækst i kornhandelen. Etableringen af Christian IX’s Bro i 1867 og Lollandsbanen i 1874 betød imidlertid, at Nysted mistede dele af sit opland til især Nykøbing F, men byen genvandt noget af det tabte, efter at den fik station i 1910. Mellem 1850 og 1920 blev der etableret en række industrier, bl.a. et skibsværft (1855), et savværk (1893) og et brostens- og skærvekompagni (1918). I denne periode fik Nysted også flere institutioner, bl.a. en realskole, en teknisk skole og en handelsskole, og i årene 1896-1918 var her også et sygehus. Kystsanatoriet blev oprettet i 1930 til tuberkuloseramte børn.
Befolkningstallet nåede sit maksimum i 1925, hvor der var 1.724 indbyggere. Herefter var der et jævnt fald til 1.229 indbyggere i 1970. Parcelhusbyggeri syd og øst for byen i 1960’erne og 1970’erne førte dog til en svag befolkningsstigning. Nysted var fra 1970 til 2006 administrativt center for den nyetablerede kommune af samme navn. Indbyggertallet lå i 2006 på 1.366. Byen satsede efterhånden stærkt på turisme, og det var derfor et stort tab, at Ålholm i 1995 blev lukket for offentligheden.
