Nykøbing M voksede formentlig frem som en bymæssig bebyggelse omkring midten af 1200-tallet. Arkæologiske fund fra denne tid kendes fra området omkring Algade, mellem Nørregade, som ledte færdslen fra det nordlige opland ind til byen, og Vestergade, der var færdselsåren for trafikken fra vest.
Arkæologiske undersøgelser ved Ringsgade/Smallegade viser, at den tidlige bydannelse nordøst for Sankt Clemens Kirke var præget af blandet bebyggelse bestående af både træ-, sten- og tørvevægshuse. Herudover vidner fund af brønde og vejforløb om reguleringstiltag, måske fra byens øvrighed. I 1200-tallet kom bymæssige funktioner, som Sankt Jørgensgården på Dueholm, der fungerede som spedalskhedshospital, indtil Dueholm Kloster overtog funktionen.
På Holmen, hvor Sankt Clemens Kirke har ligget siden slutningen af 1100-tallet, er der derimod ikke gjort fund fra ældre middelalder. Det antages, at området var ubebygget og fungerede som markedsplads indtil 1400-tallet, hvor byen voksede, og også Holmen blev bebygget. I senmiddelalderen fik byen flere byfunktioner, heriblandt et helligåndshus med tilhørende hospital og kapel i byens nordende.
Nykøbing M er opstået på det sted, hvor landsbyerne Vettels og Venner lå i middelalderen. Købstadsrettigheder omtales i 1299, men man ved ikke, hvornår de er blevet tildelt. Omkring 1370 blev johanniterklosteret Dueholm stiftet, og klosteret fik positiv betydning for byens udvikling, men der var også i mange år strid om jord og ejendom mellem by og kloster. I 1460 fik byens indbyggere ret til at fiske overalt i Limfjorden.
Efter Reformationen blev Dueholm Kloster lagt under kronen, og klosterskolen blev overflyttet til Nykøbing M og var indtil 1739 latinskole. Kongen gav skolen indtægter fra seks lokale gårde. 1500-tallet bragte fremgang til byen, men 1600-tallet tilbagegang. Krige og flere brande tog hårdt på byens økonomi, og mange blev ramt af fattigdom. Byen oplevede et stigende befolkningstal, også i perioder med økonomisk stilstand. I 1787 boede der 531, i 1801 var der 651, og i 1850 var byen vokset til 1.398 indbyggere. Med befolkningstilvæksten måtte byen udvides, hvilket skete ind i landet.
I 1460 fik byen eneret på handel på Mors, men morsingboerne respekterede det ikke. Handel og fiskeri gav fremgang for Nykøbing M, men i 1600-tallet forsvandt silden fra Limfjorden, og dette bidrog til byens dårlige økonomi. Fra begyndelsen af 1700-tallet var der igen vækst, men den gunstige handel blev forstyrret af dårlige indsejlingsforhold og et told sted placeret i Aalborg. Efter flere ansøgninger fik man i 1841 eget toldsted. Byen havde i århundreder en primitiv havn, men i 1788 fik tre privatpersoner lov til at bygge en ny; visse indtægter skulle dog tilfalde byen. I 1843 lånte byen penge til at købe havnen, hvorefter den blev udvidet og gjort dybere.
I perioden 1850-1921 steg befolkningstallet fra 1.398 til 8.352 personer. Nykøbing M’s handel blev forbedret, da Frederik VII’s Kanal ved Løgstør blev indviet i 1861. Den industrielle udvikling tog fart, og Morsø Jernstøberi blev anlagt i 1853; få år senere fulgte bl.a. klædefabrik og Morsø Bank oprettet i 1873. Der blev anlagt nye veje, og i 1873 blev der indført færgefart mellem Nykøbing M og Glyngøre. Staten overtog forbindelsen i 1885, og i 1889 blev togforbindelsen mellem Skive og Glyngøre åbnet. Dermed fik byen gode trafikale forbindelser til resten af landet.
I 1900-tallet blev havnens betydning reduceret, da varer oftere blev transporteret over land. Indbyggertallet voksede støt og nåede i 1965 op på 9.378 indbyggere, hvorefter det faldt til 9.066 i 1970. Den industri, der voksede frem i 1800-tallet, blev for en del virksomheder cementeret i 1900-tallet, hvor også handel og håndværk fortsat beskæftigede mange. I 1930’erne havde byen 220 forretninger. Nykøbing M var tidligt ude med at åbne en selvbetjeningsbutik, hvilket skete i 1949, da Brugsen gik i spidsen for udviklingen. Fra 1960’erne vandt supermarkederne terræn, og mange små butikker enten lukkede eller flyttede til hovedgaden.
I 1970 var hele kysten langs Klosterfjord bebygget med Ørodde som rekreativt område. Frem til 1990 kom der nye kvarterer mod syd, mens virksomhederne flyttede til industrikvarteret i nordvest. Toldstedet blev nedlagt i 1972. I 1977 ophørte jernbanefærgen til Glyngøre med at sejle, og året efter blev Sallingsundbroen indviet. Havnen har stadig erhvervsfiskeri, men også en stor indtægt fra lystbåde. Handel, industri og håndværk er byens største erhverv.
I 1990’erne begyndte kommunen at investere i byfornyelse og kultur, bl.a. i Fiskerbyen, et område med små huse nord for havnen, og med omdannelsen af det ældste jernstøberi til kulturhus, og der kom nye bolig- og erhvervsmiljøer.
