Село Шолдэнешть впервые упоминается в 1610 году в грамоте о размежевании границ соседствующих селений как владение боярина Писоцкого и его жены Тудоски, дочери великого логофета Патрашку Шолдана. По легенде, название города происходит от имени боярина Шолдана, который во многих битвах проявил храбрость, за что бы награжден господарем селами, в том числе и тем, которое впоследствии стало известно как Шолдэнешть. Род Шолданов был одним из самых древних в Молдове. Он, как свидетельствует Дмитрий Кантемир, существовал еще в момент основания молдавского государства. На протяжении XV–XVII веков многие бояре из семьи Шолдан занимали важные посты в княжестве.

Перепись 1817 года показала, что в Шолдэнешть были 52 крестьянских подворья, водяная мельница на реке Чорна, пашни, пастбища и сенокосы. В ходе переписи 1835 года в населенном пункте зарегистрировали 304 жителя: 166 мужчин и 138 женщин. В 1894 году на участке железной дороги Рыбница — Бельцы был открыт ряд станций, в том числе и в Шолдэнешть.

Особую роль в экономическом развитии Шолдэнешть сыграло мукомольное дело. На реке Чорна издавна строились водяные мельницы. И сейчас на берегах реки можно увидеть остатки одного из таких сооружений.

В 1904 году в Шолдэнешть насчитывалось 93 хозяйства и 283 головы крупного рогатого скота. В 1911 году была открыта почта и установлена телеграфная связь. В 1918–1940 годах Шолдэнешть являлись центром коммуны, входившей в состав Резинской волости Оргеевского уезда.

В 1863 году в Шолдэнешть была открыта приходская школа, а в 1902 году стала функционировать одноклассная начальная школа.

Самые ранние сведения о храмах в Шолдэнешть связаны с церковью Св. Архангелов, возведенной в конце XVIII века. В 1804 году в селении построили деревянный храм Св. Архангела Михаила. В 1957 году советские власти закрыли церковь, ее помещения стали использовать в хозяйственных целях. 14 ноября 1993 года храм снова открыл свои двери для прихожан.

В 1980 году Шолдэнешть придали статус поселка городского типа, а в 2002-м — города.