Nakskov opstod i 1200-tallet i bunden af Nakskov Fjord ved Halsted Ås udmunding midt i et frugtbart landbrugsland. Købmandsgårdene lå langs stræderne fra havnen mod vest til den højere liggende bykirke mod øst. Sankt Nikolai Kirke blev bygget i første halvdel af 1200-tallet. Byens ældst bevarede købstadsprivilegier stammer fra 1266, og den lå strategisk for søfart og handel i den vestlige Østersø. Nakskov var mødested ved forhandlinger mellem danske konger, hansestæderne og andre udenlandske magthavere. Kong Erik Plovpenning indgik i 1242 et forlig med den estiske ærkebiskop i byen. Naturhavnen ved Albuen, som lå længere ude i fjorden, var flådeopsamlingssted.
I 1400- og 1500-tallet klagede Nakskov gentagne gange over, at omegnens bønder, i strid med byens eneret, solgte deres landbrugsvarer uden for byen, fx ude på Albuen, hvor der blev drevet handel og fiskeri. Et helligåndskloster blev oprettet i 1470. I 1510 blev Nakskov sat i brand af lybækkere.
De mange bindingsværkshuse fra 1600- og 1700-tallet ligger formentlig samme sted som deres middelalderlige forgængere. Den middelalderlige bykerne ligger inden for 1600-tallets befæstning af Nakskov Byvold, dvs. området mellem Nørrevold, Nygade og Havnegade. Byvolden, som fastlagde byens udstrækning frem til midten af 1800-tallet, har været nogle meter høj og op til 17 m bred i tværsnit. Det kan tyde på, at gaderne i byen og ved havnen har ligget på samme sted siden middelalderen. I Dronningensstræde er der udgravet dele af et bolværk fra en havn. Vejene til oplandet på Lolland gik gennem Tilegade, Vejlegade og Søndergade. Nakskov var Lollands største købstad og rangerede skattemæssigt som den syvende i landet. Perlestikkerbogen, en regnskabs- og optegnelsesbog fra perioden 1618-27 opkaldt efter forfatteren, pastor Anders Pedersen Perlestikker, giver oplysninger om ca. 2.000 nakskovitter.
Nakskov overgav sig, da svenske tropper i februar 1658 gik over isen på Langelandsbælt. I juli 1659 blev byen dog raseret efter en fornyet belejring. Under belejringen ramte flere kanonkugler kirken, og en granat er opbevaret i Sankt Nikolai Kirke til minde. Nakskov blev i 1667 kompenseret herfor gennem eneret på al lollandsk udenrigshandel. Tilflyttere fik tilladelse til at bosætte sig og drive erhverv som fx de første jødiske tobaksspindere, der slog sig ned i 1674.
I 1787 lå indbyggertallet på 1.375, og efter år 1800 blomstrede Nakskov op med istandsættelse af havnen, uddybning af sejlløbet i fjorden og en omfattende korneksport.
Indbyggertallet blev næsten firedoblet fra 3.375 i 1855 til 13.294 i 1921. Infrastrukturen blev forbedret med faste skibsforbindelser til København og Kiel. Færgeforbindelsen mellem Langeland og Lolland blev i 1869 flyttet til købstadshavnen i Nakskov fra Tårs, og i 1874 åbnede jernbaneforbindelsen til Maribo og Nykøbing F.
Havnen, jernbanen og det frodige landbrugsopland var sammen med en relativt stor arbejdskraft medvirkende til udviklingen af næringsmiddel- og metalindustri, og Nakskov blev efterhånden en egentlig industriby. Nakskov Sukkerfabrik blev anlagt 1882-83, og i 1913 flyttede Havregrynsfabrikken til Nakskov fra Maribo; den fik i 1915 navnet OTA. Derudover blev Nakskov Skibsværft stiftet i 1916. Industrikvarterer og nye boligkvarterer blev anlagt i en bræmme rundt om den ældre befæstningsby.
Det kom i 1931 til regulære gadekampe mellem på den ene side politi og militær og på den anden side arbejdere og arbejdsløse i Nakskov; baggrunden var en arbejdsløshed, der var fordoblet på bare et år. I årene efter 2. Verdenskrig fortsatte befolkningstilvæksten. I 1945 boede der 15.787 i Nakskov, og indbyggertallet toppede i 1960 med 16.935. Nakskov blev regionens vigtigste industriby, og havnen blev Lollands største udskibningshavn med eksport af landbrugsvarer til England. I skibsværftets storhedstid i 1960’erne var der over 2.000 ansatte.
Byplanstrukturen fra 1950’erne med store indfaldsveje ind til bymidten var grundlaget for udbygningen af Nakskov. Nye byområder med adskilte parcelhus-, etage- og erhvervsområder opstod rundt om den gamle by.
Indbyggertallet fortsatte med at falde fra 1960, og i 2006 lå det på 14.240. På trods af dette forblev Nakskov Lollands største by. Sukkerfabrikken forblev en central del af byen ved fjorden, mens byen blev ændret fra industriby til administrations- og serviceby. I forbindelse med Kommunalreformen i 1970 blev Nakskov administrativt center i kommunen af samme navn. Færgeoverfarten til Langeland flyttede i 1975 fra Nakskov tilbage til Tårs. Nakskov Uddannelsescenter samlede i 1979 alle byens ungdomsuddannelser på Søvej. Skibsværftet måtte efter mange års krise lukke i 1987.
