Перші письмові згадки про Кам’янку датуються 1406, 1411 роком. Тоді поселення називалось Димошин.
З середини XV століття почало називатись Кам’янка-Струмилова за прізвищем власника — львівського підкоморія Юрія Струмила. У 1471 році місто отримало магдебурзьке право. Юрій Струмило, як власник міста, фундував та надав засоби для римо-католицької парафії міста.
Наприкінці XV ст. Кам’янка-Струмилова була центром торгівлі та ремесла. Через місто пролягали торговельні шляхи з Києва до Польщі та з Волині на Львів. Двічі на рік тут проводили ярмарки, щотижня відбувалися торги. 1578 р. місто одержало право складу для дрогобицької солі. У місті діяли цехи кушнірів, ковалів, шевців, гончарів, слюсарів, мечників. Тут було 400 будинків.
Татарські напади наприкінці XV — на початку XVI ст. знищили місто, воно втратило давні привілеї, але 8 квітня 1509 р. король Польщі Сигізмунд I Старий наново підтверджує міські права Кам’янки.
У податковому реєстрі 1515 року в місті документуються 2 попи (отже, уже тоді були 2 церкви) і міський млин.
У XVI—XVII ст. із Кам’янеччини вивозили за кордон волів. Вивіз худоби — одна із найприбутковіших галузей польської шляхти. Селяни Кам’янко-Струмилівського староства 1636 року відмовились відбувати панщину. Особливо ж гостра боротьба проти соціального і національного гніту розгорталася під Хмельниччини 1648–1657 років. Тоді місто було зруйноване, населення пограбоване.
У XVIII столітті місто поступово відродилося і залишилося центром ремісничого виробництва. Тут працювали кушнірський, шевський, ткацький, ковальсько-слюсарний, бондарський, гончарний, столярно-токарський та ливарно-мечницький цехи, а також цех рибалок. У 1880 році населення Кам’янки-Струмилової становило 6107 осіб. У місті діяли цегельний завод, винокурня, паровий млин, лісопильний завод, на якому виготовляли паркет, смолу, терпентин і деревне вугілля. У 1900 році єврейське населення Кам’янки-Струмилової становило 3549 осіб.
У 1892 році парох і декан міста отець Михайло Цегельський виступив ініціатором створення філії українського товариства «Просвіта» у Кам’янці-Струмиловій.
За австрійських часів Кам’янка-Струмилова мала: залізничну станцію, повітовий уряд, міську управу, суд, пошту, телеграф, податковий уряд, позичкові каси, аптеку і два парафіяльні уряди: греко-католицький і римо-католицький.
До початку Першої світової війни у місті дислокувався ІІ дивізіон 9-го полку драгунів австро-угорської армії, який вирізнявся найбільшим відсотком українців серед решти драгунських полків.
Український Громадський комітет (о. Михаїл Цегельський, Роман Петрушевич — молодший брат Президента ЗУНР, — І. Вертипорох та інші) роззброїли вояків старшинської школи у місті. Під керівництвом старшин Ю.Шепаровича, В.Назаревича, О.Косаревича 70 курсантів-українців та близько 300 селян, робітників, ґімназистів взяли владу в повіті.
Українці Кам’янки-Струмилової радісно вітали проголошення Західно-Української Народної Республіки. Перебравши владу в місті, українці призначали на найважливіші пости своїх людей. Повітовим комісаром став суддя Роман Петрушевич. У березні 1919 року у місті почала виходити газета «Козацький голос» — орган Начальної команди УГА. Було відкрито українську школу, яка містилася у ратуші, діяв театральний гурток, засновані хор, філія товариства «Українська Бесіда». Місто мало свій часопис «Камінецькі Вісті».
14 жовтня 1933 року розпорядженням міністра внутрішніх справ місто збільшене за рахунок сіл Кривулянка і Підзамче Кам’янко-Струмилівського повіту та включення їх до міської гміни Кам’янка-Струмилова.
Українське національне відродження кінця XIX — першої половини XX століття охопило усі сфери духовного та господарського життя Кам’янеччини, але події вересня 1939 року перекреслили усі сподівання українців на краще, самостійне життя. Трагедія України 1940-х років, придушення національних прагнень українців у подальші десятиріччя з усією повнотою позначилися на житті Кам’янеччини. Проте, незважаючи на важкі часи Підрадянської України, у цьому регіоні розвивалося сільське господарство та промисловість, освіта і культура.
