Перше поселення на місці сучасної Новоселиці, яка є адміністративним центром району, виникло на сухопутному торговому шляху, що проходив у ХІІ — ХІV століттях з Галича до Берлада на Дунаї. Вперше населений пункт згадується в документах 1456 року, як "Шишківці, де був Юріїв двір".
Індустріалізація наприкінці XIX століття сприяла стрімкому розвитку Новоселиці. Тут побудували два шкіряних заводи, олійницю, паровий млин, винокурню та свічко-миловарний завод. На початку ХХ століття населення Новоселиці зросло до 10 тисяч жителів, переважна більшість з яких була євреями. На той час в містечку діяли 10 синагог і дві православних церкви.
На жаль, до сьогоднішніх днів у місті збереглося мало пам’яток архітектури. Однією з найцікавіших є будівля залізничного вокзалу, збудована в 1905 році у російській частині міста. Саме звідси у 1915 році американський письменник-публіцист Джон Рід почав свою знамениту подорож Російською імперією, а свої враження про Новоселицю він описав в книжці "Війна у Східній Європі".