Територію сучасного Теофіполя в стародавні часи заселяло слов’янське плем’я — волиняни. У IX—X ст. вона входила до складу Руської держави з центром у Києві, а з 1199 року — до складу удільного Галицько-Волинського князівства. В XIII ст. цю місцевість захопили і спустошили монголо-татари.
У другій половині XIV ст., на початку Великої зам’ятні у Золотій Орді (1359-1380), після битви на Синіх Водах (1362), перейшло під владу Великого князівства Литовського, Руського та Жемойтського.
Теофіполь під назвою Камінь, як одна з фортець — опорних пунктів литовських феодалів на півдні Волині, вперше згадується 1420 року в дарчому акті великого князя литовського Вітовта. Назва Камінь, очевидно, пов’язана з поселенням, що виникло як камінне оборонне укріплення. З трьох сторін його захищали озеро та річки Полква і Норець.
У XV і в першій чверті XVI ст. Каменем володіли волинські шляхтичі Човганські (Чолганські). Містечко стали називати Човганським Каменем, щоб відрізнити його від містечок і сіл з такою ж назвою, яких на Волині було багато. Пізніше в народі закріпилась назва Човган (пол. Czołhan). Багаті землі Човганського Каменя і його околиць приваблювали волинських шляхтичів та магнатів. Цей маєток був предметом постійних суперечок і боротьби між феодалами: шляхтичами Сенютами та князями Острозькими. 1624 року К. Сенюта купив Човганський Камінь, але фактично ним володіли багатші і впливовіші магнати князі Острозькі.
У середині XVI ст. у Човганському Камені певного розвитку набули промисли, зокрема горілчаний, борошномельний, деревообробний. У містечку було дві гуральні, два водяні млини, працювало кілька десятків ремісників. Тяжко жилося кріпакам. Панщина сягала 4—5 днів на тиждень. 1569 року Човганський Камінь загарбала шляхетська Польща, його було включено до Кременецького повіту Волинського воєводства. Кріпосницький гніт посилився національними і релігійними утисками. Населення чинило цьому впертий опір. У 1594—1596 рр. жителі Човганського Каменя брали активну участь в антифеодальному повстанні, яке очолив Северин (Семерій) Наливайко.
Поблизу Човганського Каменя проходив Чорний шлях, по якому татари набігали на українські землі. Особливо великого спустошення містечко зазнало в 1593 і 1618 роках.
Населення містечка та його околиць брало активну участь у визвольній війні 1648—1657 рр. Польсько-шляхетське військо безжалісно грабувало жителів, вбивало жінок, дітей, садило непокірних на палі. Селяни відмовлялися збирати урожай на панських ланах, виконувати інші повинності, їхні загони виступали проти шляхетських військ і поміщиків. У серпні 1648 року польські комісари (командуючі військами) в своїх посланнях скаржилися польському урядові, що в районі Човганського Каменя вони зустрічають великий опір повсталих селян. 28 і 29 серпня 1648 року Богдан Хмельницький надіслав у Човганський Камінь командуванню ворожих військ два листи з вимогою припинити варварські знущання над українським населенням, з яким особливо жорстоко розправлялося військо, очолюване князем Єремією (Яремою) Вишневецьким.
Перед Пилявецькою битвою (вересень 1648 р.) Я. Вишневецький у листі, відправленому з Човганського Каменя, просив свій уряд, щоб туди спорядили нові військові сили «для знищення домашнього ворога» — українського війська і повсталих селян, а польський комісар Адам Кисіль у свою чергу писав звідси: «Вже й тут довкола оточили нас полки Хмельницького».
Після розгрому під Пилявцями рештки шляхетських військ тікали через Човганський Камінь. Добивати їх допомагали місцеві повсталі селяни.
Селяни продовжували боротьбу і в наступні роки. 21 червня 1649 року до Човганського Каменя прибув Богдан Хмельницький. Тут він чекав підходу своїх полків, після чого вирушив на Збараж, де укріпились польські війська. До військ Хмельницького приєдналось все доросле чоловіче населення містечка і навколишніх сіл. 9 липня біля Човганського Каменя українська армія розгромила головні сили польських військ. Запеклі бої проти польсько-шляхетських військ вели козаки і повсталі селяни в районі Човганського Каменя і в 1653 році.
У середині і другій половині XVII ст. містечко не раз зазнавало нападів кримських татар. У серпні 1649 року татари спустошили Човганський Камінь і навколишні села.
Після закінчення визвольної війни польська шляхта посилила соціальний, національний і релігійний гніт українського народу. Тяжких знущань зазнали трудящі Човгана, які разом з українськими військами активно діяли проти польських панів. В 1664—1665 рр. човганці брали активну участь в антифеодальному повстанні на Поділлі в загоні, яким керував Семен Височан, а в 1702—1704 рр. — у повстанні під проводом Семена Палія. 1709 року у містечку знову спалахнуло повстання, під час якого селяни вбили поміщика — орендаря Б. Вільгу.
1681 році поміщик К. Сенюта продав Човган разом з селянами за 75 тис. злотих польському магнатові Станіславові Янові Яблоновському (великий коронний гетьман, краківський каштелян, воєвода руський), якому належало 18 міст і 150 сіл.
Човган перейшов до його сина, Александра Яна Яблоновського, а по його смерті 1723 року до його удови, Теофілії з Сенявських, за якої виникла назва Теофіполь. З метою поширення католицького обряду поміщиця побудувала у Човгані костьол і двоповерховий монастир тринітаріїв. В 1740 році вона перейменувала Човган на Теофіполь (у тогочасних польських джерелах — Теофільполь). З 1777 року стала володіти княгиня Теофілія Яблоновська (1742—1816, пол. Teofila Strzeżysława Jabłonowska, дочка Юзефа Александра Яблоновського, кревна сестра «князя-козака» Августа Доброґоста Станіслава Вольфганґа Жеґоти Яблоновського), з 1761 року дружина Юзефа Сапеги (1737–1792). В палаці поміщика в окремих покоях утримувалось багато собак, а також папуг та інших птахів. У Сапеги ломилися скрині від діамантів, коралів, хутра і всякого добра. В палаці часто влаштовувалися пишні бали, на які князь витрачав великі кошти. В той же час містечкова біднота йшла в злиднях, щодня шукаючи шматка хліба. За даними ревізького перепису в 1794 році у Теофіполі 65 селянських сімей не мали не тільки землі, коней, корів, а навіть примітивного житла.
Обдирали трудящих і церковники, які нічим не гребували. Так, на кошти населення в 1764 році у Теофіполі побудували Покровську церкву, а пізніше ще два храми.
Теофіполь знаходився на великому торговельному шляху із Західної України в Росію. Це сприяло розвиткові торгівлі. З містечка вивозили хліб, худобу, сало, м’ясо, горілку, а ввозили сільськогосподарський інвентар, залізні вироби, тканини. У XVIII ст. Теофіполь був осередком поміщицького гуральництва. З 1797 року після анексії Російською імперією містечко стало центром Теофіпольської волості Старокостянтинівського повіту Волинської губернії.
Наприкінці XVIII і в першій половині XIX ст. у містечку певного розвитку набуло промислове й ремісниче виробництво. У 1795 році тут жило 144 ремісничі родини. У 1845 році в Теофіполі вже діяли три шкіряні, цегельний і вапняковий заводи. Вони були дрібні, напівкустарні, переважала тут виснажлива ручна праця, а робочий день тривав по 12—14 годин.
Після польського визвольного повстання 1830—1831 рр., в якому взяли участь служителі тринітарського монастиря, вчителі повітової школи і поміщик, князь Леон Сапега, царські власті закрили у Теофіполі школу, монастир, конфіскували маєток Сапегів, а селян перевели в розряд державних. У 1850 році 56 безземельних селянських сімей примусово виселено в державний маєток до с. Малого Лазучина, бо, як зазначалося в акті про виселення, у Теофіполі не було для них вільної землі.
Станом на 1886 рік в колишньому державному містечку, центрі Теофіпольської волості Старокостянтинівського повіту Волинської губернії, мешкало 1160 осіб, налічувалось 201 дворове господарство, існувала православна церква, синагога, 5 єврейських молитовних будинків, школа, 11 постоялих дворів, 14 постоялих будинків, 52 лавки, кузня, 3 водяних млини, миловарний і цегельний заводи.
За переписом 1897 року кількість мешканців зросла до 3774 осіб (2402 чоловічої статі та 1372 — жіночої), з яких 1372 — православної віри, 2914 — юдейської.
Під час радянсько-української війни 1917—1921 років у 1919 році існувала «Теофіпольська республіка», яка не підтримувала відкрито ні однієї із сторін, проте на початку червня при переході українських сил в наступ, теофіпольські повстанці вдарили червоним в тил.
У грудні 2015 року освячено храм УПЦ КП пам’яті святителя Миколая Мир Лікійських.
17 липня 2016-го Святійший Патріарх Філарет очолив чин освячення новозбудованого храму на честь Покрову Пресвятої Богородиці та першу Божественну літургію
