Місто Кам’янка-Бузька до 1944 р. мало назву Кам’янка-Струмилова. У писемних джерелах вона вперше згадується 1441 р. Першу частину своєї першопочаткової назви місто отримало від річки Кам'янки (притока Західного Бугу), на якій воно стоїть, а другу — від імені міського старости Юрія Струмила, який доклав чималих зусиль до розвитку та укріплення міста у XV ст. Тоді ж Кам’янка-Струмилова отримала магдебурзьке право та статус вільного міста.
У часи Середньовіччя Кам’янка була дерев’яною фортецею, оточеною земляними валами та ровами.
Історія Кам’янки-Бузької пов’язана також із зародженням українського театру.
Дві інтермедії з трагедії Якуба Гаватовича (1598-1679) є найдавнішими українськими драматичними творами, тексти яких дійшли до наших днів. 29 серпня 1619 р. на міській площі Гаватович разом зі своїми учнями під час ярмарку поставив драму власного авторства "Трагедія, або Образ смерті пресвятого Іоана Хрестителя, посланця Божого". Дійові особи трагедії розмовляли польською мовою. Але після 2-го та 3-го актів були представлені дві українські інтермедії на теми народних анекдотів — "Продав кота у мішку" та "Найкращий сон".
Саме в Кам'янці у 1913 р. актори професійного українського театру товариства "Руська Бесіда" вперше поставили драму І. Франка "Украдене щастя" за оригінальним (нецензурованим) текстом. Серед цих акторів був Лесь Курбас.
Окрім цікавих пам'яток архітектури, варто просто прогулятися центром міста — тут розміщені старі кам'яниці та вілли ХІХ-ХХ ст. Для відпочинку у місті є також парк.