Місто закладене на місці колишнього поселення Доброщани, яке перед тим було знищене татарами. Дозвіл на будівництво поселення та дерев’яного замку, як і Магдебурзьке право, були надані Стефаном Баторієм в Любліні 24 серпня 1584 року. Замок був приблизно такий, як на той час в Сатанові, Городку, Гусятині, Ярмолинцях, Зінькові, Чорному Острові. На свято трьох Королів (Йордань) та на Святу Трійцю у містечку відбувались ярмарки, більше того — Стефан Баторій звільнив поселенців від податків та повинностей.
Залишки замкових валів досі можна побачити — вони оточують шкільний спортивний майданчик.
Фельштин кілька разів був зруйнований татарами, а в 1615 році тут розмістився табір хана, і звідси в різних напрямах татари атакували довколишні села. Після Гербуртів частини їх спадщини (Купин, Кремінна, Лісоводи) перейшла до Стадницьких, а Фельштин з околичними селами дістався дружині Яна Гербурта.
У 1680 році село дісталося османській Туреччині, на його полях проходив кордон.
17 лютого 1729 року Фельштин разом із 12 околичними селами Стшеменським був проданий Бернардові Граб’янці. Родина Граб’янок опікувалася Фельштином. В містечку великого значення набули об’єднання, котрі називалися ремісничими цехами.
У 1900 році в селі не було ніяких промислових підприємств, і багато чоловіків та жінок наймалися на сезонні роботи на цукрові заводи Деражні.
Містечко Фельштин стало центром Фельштинського району, який існував до 3 лютого 1931 року. Згідно з постановою ВУЦВК від 3 лютого 1931 року було проведемо укрупнення районів на території нинішньої Хмельницької області і Фельштинський район увійшов до складу Городоцького. Постановою ВУЦВК СРСР від 22 вересня 1937 року утворено Кам’янець-Подільську область, у складі якої у жовтні 1939 року відновився Фельштинський район.
У Фельштині проживала значна частка євреїв. У ХІХ столітті тут проживало 2994 особи, з них євреїв — 1220. Євреї у містечку переважно були перекупниками худоби, торгівцями в крамницях, шили одяг та обробляли шкіри. У Фельштині навіть були дві сільські Ради: українська та єврейська. Майже всі вони були знищені у 1942 році в Гелетинському лісі.
