Det er højst sandsynligt, at Nysted skylder Aalholm sin oprindelse. I den tidlige Middelalder var Lolland og fortrinsvis selvfølgelig dens Sydkyst meget udsat for Hærgning af genboerne hensides Østersøen, Venderne. Rimeligt er det derfor, at Befolkningen valgte en Byggeplads, hvor de kunde finde Beskyttelse, og en saadan må den befæstede Borg have kunnet yde.
Nysteds Beboere var derfor også oprindelig vornede under Aalholm, men 1409 blev de frie, idet Erik af Pommeren skænkede dem Købstadsrettigheder, der 1513 blev stadfæstet af Christian den Anden. Ligesom andre Købstadborgere sluttede Nystederne sig til Chr. II's Parti, og i Grevens fejde overrumplede de 1534 Aalholm Slot, da Lensmanden Jørgen von der Wisch var fraværende, og overgav det til Grev Christoffer, som beholdt det i to Aar.
Nedenfor vises Afskrift efter en Kopi i et haandskrevet Eksemplar af Resens Atlas, der opbevares i Det Kgl. Bibliotek Retskrivning og Stil let moderniseret i Afskriften.

" Vi Erich med Guds Naade Danmarks, Sveriges, Norges, Venders og Goters Konge, Hertug i Pommeren hilse alle Mænd, der se, høre eller læse dette vort Brev, evindelig med Guds og vor Naade og kundgøre for alle Mænd saavel de, der nu ere, som de, der end komme skulle, at vi ved nærværende Brev give vore kære Borgere af Nystade i Lolland fri og frelse for alle Haande Arbejde og Skat, som de hertil have været vante at give og gøre til vort Slot Aaleholm, og saadan frihed unde vi Boe Laurenszen og Lybiche Brynne og alle andre, paa det forskrevne Gods bo og bygge, og den Skat, de skulle give, den skal vore Bymænd af Nysted til Hjælp komme i den Skat, som de os hvert Aar give skulle, med saadanne Vilkaar, at de skulle os hvert Aar efter den Dag give til Skat halvfemtesinds tyve lybske Mark, to Læster Byg eller Malt, og dertil skulle de os give af hvert Skib, som til Sildefiskeri farer, én Tønde Sild. Item unde vi dem, at de maa faa det Stræde fri, som de os have ombedet; item unde vi dem Fægang og Ildebrand, saasom de hertil have haft. Item ville vi, at alle disse stykker skal evig blive, og ingen Mand skal dem Magt have i andre Maader at vende uden vi eller den, som Konge efter os i Danmark vorder. Item forbyde vi alle vore Høvedsmænd, Fogder, Ombudsmand og alle andre, hvor helst de ere, at de ikke forskrevne vore Borgere over disse vore Naader i nogen Maade forurettte. Til Vidnedbyrd er vort Sekret hængt for dette Brev, skrevet paa vort Slot Nyborg under vor Herres fødselsaar Tusinde fire Hundrede paa det niende, den Lørdag næst efter S. Nicolai Dag."

Det ældst kendte segl for Nysted viser et på bølger stående skib af den gamle nef-type med korsprydet mast støttet af 4 stagtove uden sejl og udstyr med højst svungne stavne mellem opvoksende indadbøjede planter med store blade. Det kendes fra et brev dateret 22/7 1535. Omskriften er delvis ødelagt, rester og pladsforhold tillader udfyldningen:

SIGILLUM CIVIUM DE VIRBE NIESTED

oversat: Segl for borgerne fra byen Nysted. Både bladenes former og skibstypen viser, at seglet må være udført efter forbillede ældre end 1241. Derved stemmer, at seglet ikke viser Ålholm, hvad det utvivlsomt ville have gjort, om det var yngre end slottets anlæg ca. 1242-48. I en henføring af seglet til tiden før 1241 er der ikke noget umuligt - jfr. tidligere påvisning af tilsvarende alder for seglene fra Varde, Åbenrå, Tønder, Kolding o.s.v. Nævnes kan også Roskilde Domkirkes ældste segl, der er fra før ca. 1150.
Byen må have fået stor betydning efter Valdemar II's erobring af Holsten 1201 med nye privilegier til Lybeck af 26/11 1202. Og da denne bys segl synes at have været benyttet som forbillede, må en henføring af byens segl til ca. 1205 anses for den mest naturlige.

I byens næste segl, der tidligst kendes fra brev dateret 1/6 1584, er skibet moderniseret til et handelsskib med kasteller for og agter, 3 korsprydede master støttet af stagtove både over og under en udkigskurv på midtermasten. Uden segl og uden planter. Her er omskriften:

SIGILLUM CIVIUM DE NEAPOLIENS

hvor sidste ord er en forkert latinisering af det til byens latinske navn svarende indbyggernavn, der naturligvis heller ikke kan stå efter DE, blot sideordet CIVIUM. Skibstypen er her fra 1500-årene. Stampen udført af Jacop Ebbesøn 1584.