Les premiers colons russes s'établirent sur le territoire de l'actuelle Nevelsk en 1789. Après la signature du traité de Shimoda, en 1855, la colonie, sous le nom de Honto, reçut une administration conjointe russo-japonaise, puis uniquement russe. Par le traité de Portsmouth, qui mit fin à la guerre russo-japonaise de 1904-1905, tout le sud de l'île de Sakhaline, devint japonais, y compris Honto.
En 1912, la première usine pour le traitement du poisson fut ouverte à Assanaï, à 20 km au sud, au bord de la rivière Assanai. Entre 1916 et 1927, fut créé ici le premier port de l'île libre de glace en hiver. Après la Seconde Guerre mondiale, la localité passa sous la souveraineté de l'Union soviétique et reçut le statut de ville le . Elle fut renommée Nevelsk en hommage à l'amiral et explorateur russe Guennadi Nevelskoï.
Le , la ville subit un tremblement de terre de magnitude 6,8 sur l'échelle de Richter, suivi par un petit tsunami. Le séisme fit douze morts et deux blessés graves, et laissa environ 2 000 personnes sans logement.
Population
Recensements (*) ou estimations de la population[1]:
Nevelsk est l'un des centres de l'industrie de la pêche de l'île de Sakhaline et la base opérationnelle de la flotte de chalutiers. De la houille est exploitée près de la ville. Grâce aux courants marins chauds, qui baignent la côte occidentale de l'île, et aux hautes montagnes qui la protègent des vents de l'est, Nevelsk bénéficie d'un climat relativement doux et la région a été surnommée la « Crimée de Sakhaline ». L'agriculture y est active : pommes de terre, légumes, fruits, lait, bétail. La ville s'efforce de développer le tourisme : observation des animaux (otaries, flamants roses), plongée sous-marine, plaisance. Mais la situation économique et sociale de la ville demeure mauvaise.