Localitatea își trage denumirea de la un tânăr boier cu numele Șoldan. Printr-un document din 22 septembrie 1411, Alexandru Voievod dăruiește lui Petru Șoldan, soției sale (fiica boierului Ghiulea Pântece) și fratelui său Miclăuș sălașele tătărești de la Tamârtășăuți pe Șomuz, după care numele de odinioară al localității a fost schimbat după numele proprietarului: Șoldănești. Neamul Șoldăneștilor este unul din cele mai vechi din Moldova, contemporan descălecării. 

În anul 1835 în Șoldănești locuiau 304 de suflete; multe decenii la rând, datorită războaielor și a situației economice dificile, populația localității nu a cunoscut o creștere semnificativă. După reforma agrară din 1868 în localitate s-au dezvoltat 68 de gospodării țărănești. Odată cu construcția căii ferate, la sfârșitul sec. XIX, în Șoldănești începe să se dezvolte viața economică. La începutul sec. XX, în localitate apar primele elemente industriale: moară cu aburi, fabrică de var, etc.

În anul 1927 a început să funcționeze fabrica de fermentare a tutunului, care în anul 1986 a atins volumul maxim de producție – peste 15 mii tone de tutun fermentat. Localității i s-a conferit statut de orășel în noiembrie 1980. Începând cu anii 1990–1992 populația orașului prin repetate rânduri de donație au contribuit la reparația bisericii. Petru Ion Gojan a construit în curtea bisericii o casă parohială și o frumoasă fântână acoperită cudantelă de țiglă. La deschiderea bisericii serviciul divin a fost oficiat de Mitropolitul Vladimir (Mitropolitul Chișinăului și întregii Moldove) însoțit de un Sobor de preoți din capitală.