Історія ансамблю починається ще 1938 року в місті Кам’янець-Подільський. Колектив стартував як хорова капела, до складу якої входили найкращі аматорські й професійні артисти.
1945 року хор переїжджає до нового обласного центру — Проскурова. 1954 року Проскурів перейменовують на Хмельницький. Хор реформують у ансамбль пісні і танцю під назвою «Подолянка», і він працює під цією назвою до 1989 року. 1989 року, з ініціативи Миколи Балеми, який керує ансамблем з 1975 року, колектив перейменовують на «Козаки Поділля».
Упродовж трьох десятиліть ансамбль перебував у постійному творчому пошуку, що й сформувало його впізнаваний мистецький стиль. Завдяки ретельному вивченню подільських українських народних пісень і танців ансамбль зумів сформувати репертуар, у якому фольклор поєднується із сучасною музикою.
Основою репертуару ансамблю насамперед є місцевий фольклор. Щороку кількість народних пісень у репертуарі колективу також зростає завдяки роботам фольклористів, таких як Настя Присяжнюк, Гнат Танцюра, Родіон Скалецький, Марія Руденко, Зоя Чорна та інші. Загалом фольклорний матеріал Поділля доволі «барвистий», різноманітний і веселий. Наприклад, є комічні, грайливі пісні, які на Поділлі називають «чабарашками» чи «шумками», що по суті є аналогом карпатських «коломийок».
Наразі колективом керує хореограф Олена Єфімчук. Цікаві постановки завжди виконуються на високому професійному рівні. Серед них: «Подільські вечорниці», «Гопак», «Проводи козака», «Козацький квадрильйон», «Кривий танець», «Василечки», «Козацька рада» тощо. Через свої постановки ансамбль представляє все найкраще з невичерпної скарбниці народного мистецтва з усіх регіонів Поділля. Щирі пісенні твори, веселі танці, віртуозна народна музика, авангард і автентичність — усе це визначає «Козаків Поділля».
2015 року Ukrainian Dance World у партнерстві з Cobblestone Freeway Tours запланувала майстер-класи з «Козаками Поділля» в межах щорічного Ukrainian Dance Workshop Tour. У цьому турі учасники отримують унікальну можливість вивчати традиційні танці різних регіонів безпосередньо з першоджерел — від місцевих фольклорних ансамблів і лише найкращих хореографів.
