Se conoce la existencia de la localidad desde 1137, cuando un documento de Sviatoslav Ólgovich la menciona como un pogost llamado "Toshma" (Тошма), perteneciente a la recién establecida república de Nóvgorod. Sin embargo, el lugar exacto de la sede de aquel pogost se desconoce, y la primera referencia geográficamente definida de una localidad data del siglo XV, cuando diversas familias de la zona se establecieron a unos 2 km de la actual ciudad para extraer sal. Con el tiempo, el asentamiento formado comenzó a ser una de las principales fuentes de sal de Rusia, funcionando como un posad, sede de su propia vólost. Entre 1539 y 1541 fue atacado el asentamiento por los tártaros del kanato de Kazán, lo que llevó a que en la ubicación de la actual Totma se construyera una fortificación para defender las salinas.^[3]​^[4]​

En el Zarato ruso, el asentamiento fortificado de Totma se convirtió en un punto estratégico para la ruta comercial de Moscú a Arcángel. Por este tramo de la ruta del Dviná Septentrional llegaban a pasar hasta mil barcos al año. En el siglo XVIII, sin embargo, perdió su importancia para el transporte al desarrollarse el puerto de San Petersburgo, y las salinas de Totma tampoco podían competir con las nuevas salinas halladas en torno a los lagos Eltón y Baskunchak. Ante la decadencia económica que esto produjo, los barqueros de Totma comenzaron a organizar expediciones a Siberia, el Lejano Oriente y las costas de Norteamérica, que se extendieron a lo largo de la segunda mitad del siglo XVIII. Eran tanto expediciones de exploración geográfica como comerciales, y llegaron a generar una cantidad importante de dinero, que permitió construir varias iglesias notables en la localidad. Catalina II le dio el título de ciudad en 1780 y el escudo de armas en 1785.^[5]​^[6]​

Los marineros de Totma fueron muy activos en la Compañía ruso-americana y fueron los primeros europeos en explorar varias de las islas Aleutianas y Komandórskiye. Iván Kuskov, navegante nacido en Totma, fundó en California en 1812 la fortaleza Fort Ross, el asentamiento más meridional de la América rusa. A lo largo del siglo XIX, la actividad de exploración fue decayendo, y Totma pasó a ser una ciudad convencional, cuya economía se basaba en ser la sede de un uyezd en la gobernación de Vólogda. En 1904 se abrió aquí una escuela de fabricación de juguetes de madera y artículos del hogar, que hizo que la ciudad se orientara hacia la industria maderera en las décadas siguientes.^[7]​^[8]​

La Unión Soviética estableció el raión de Totma en 1929, cuando se definieron los raiones del krai del Norte. El periodo soviético supuso una destrucción parcial del patrimonio histórico que había conseguido la ciudad en los siglos anteriores, con iglesias que llegaron a ser demolidas y otras reutilizadas con otros fines. A partir de la década de 1970 comenzaron a realizarse trabajos de investigación histórica sobre el conjunto monumental de Totma, y con el tiempo el conjunto barroco de la ciudad ha sido reconocido por las instituciones. En 2010, el gobierno federal seleccionó a Totma como una de las cuarenta ciudades rusas que ostentan el título de "asentamiento histórico de importancia federal". En la decisión influyeron hechos como la conservación de gran parte de su casco histórico, la importancia que tuvo en la exploración marítima y el hecho de haber sido lugar de residencia de varios escritores destacados del siglo XIX, como Aleksandr Veltman, Piotr Lavrov y Oleksandr Koniski.^[9]​^[10]​