Nykøbing er formentlig anlagt omkring år 1200, og fra 1240 havde byen købstadsstatus. Byens opland var afgrænset af den afsondrede beliggenhed på en halvø, og byen forblev en af landets mindste købstæder. Fiskeri, især efter sild, havde stor betydning i middelalderen. Byens teglstenskirke er fra ca. 1225.
I 1672 skal byen have haft 463 indbyggere, og dette tal faldt de følgende årtier; ved den første folketælling i 1787 havde byen 532 indbyggere. Kornhandel med Norge spillede en vigtig rolle, men havnens dårlige stand gjorde, at man måtte laste og losse skibene ude på fjorden, og mange af bønderne i den sydlige del af Odsherred afsatte ulovligt deres korn til Holbæk og Kalundborg. Byens latinskole, der blev grundlagt i 1591, blev nedlagt i 1740 og erstattet med en anden skole.
Der var i 1850 1.282 indbyggere i Nykøbing S. Byens havn var en god, naturlig havn, men først ved midten af 1800-tallet fik byen et egentligt havneanlæg. Odsherreds Jernbanes åbning i 1899, der sikrede forbindelse til Holbæk, resulterede ikke i en stor udvidelse af byens industri, der bestod af jernstøberi, brændevinsbrænderier og andre mindre virksomheder. Anlæggelsen af banen førte dog til, at der kom sommerhuse i området, hvis beboere brugte byen som handels- og trafikcentrum. I 1901 boede der 2.000 personer i Nykøbing S. Byen fik råd-, ting og arresthus (1868), sygehus (1877), sindssygehospital (1913‑15), teknisk skole (1877) og realskole (1894) samt museum (1909‑10). Der kom gasværk i 1899, vandværk i 1909 og elværk i 1914.
I de første årtier af 1900-tallet blev byens indbyggertal fordoblet fra 2.100 i 1911 til 4.058 i 1930, bl.a. som følge af Statshospitalets anlæggelse. I den del af Højby Sognekommune, der grænsede op til Nykøbing S, voksede en ny forstad, Nyledsbakken, frem fra 1930’erne. I 1950’erne og 1960’erne var Odsherreds Andelssvineslagteri sammen med et maskinsnedkeri og nogle ægpakkerier byens største virksomheder. Også Sindssygehospitalet med 371 ansatte og det stigende antal turister spillede en stor rolle for byens økonomi. Byen fik handelsskole (1921), alderdomshjem (1936) og vuggestue (1969). Nordgårdsskolen blev indviet i 1968.
I forbindelse med Kommunalreformen i 1970 blev Nykøbing S administrativt center for Nykøbing-Rørvig Kommune. Befolkningen voksede fra 4.996 i 1970 til 5.317 i 2006. Samtidig blev velfærdsinstitutionerne udbygget med bl.a. friluftsbad (1970), plejecenter (1975), idrætshal (1977) og Pakhuset med udstillingslokaler, bibliotek og aktivitetscenter (1989). Da udbygningen af sommerhusområderne fortsatte, fik turismen en stadig større rolle for byen. Serviceerhverv, detailhandel og håndværk blev hovederhvervene.
