Свою историю музей ведет от Кубанского Войскового этнографического и естественно-исторического музея, который был основан в 1879 г. при Кубанском областном статистическом комитете региональным историком, войсковым старшиной Евгением Дмитриевичем Фелицыным (1848-1903). Современники называли Фелицына «энциклопедией Кавказа», «живой летописью». Он в совершенстве знал историю и географию края, археологию и этнографию, картографию, изучал геологию, ботанику и минералогию.
Первыми экспонатами музея стали подарки, пожертвования населения и личные собрания Е.Д. Фелицына по археологии и этнографии. На их приобретение Фелицын тратил своё небольшое жалование, часто влезая в долги. Музей обязан ему одной из лучших в мире коллекций каменных «половецких» изваяний, которые он свозил на подводах со всей Кубанской области. Только за первый год численность коллекции составило 276 предметов по археологии и 42 предмета по этнографии.
В стремлении изучить древнюю историю народов, населявших Северный Кавказ, Фелицын с большим энтузиазмом занимался выявлением и сбором археологических памятников. В 1879 г. он обнаружил в Екатеринодаре и отправил в Москву две греческие плиты, считавшиеся уже потерянными для науки, на которых значились имена Левкона, царя синдов, и Ксеноклида (IV в. до н.э.). Фелицын является автором уникальной археологической карты древностей Кубанской области, изданной в 1882 году Императорским Московским археологическим обществом.
Особо бережное отношение Евгений Дмитриевич проявлял к памятникам русской истории, памятным местам. Осенью 1879 года Фелицын совершил поездку в Тамань, где провел изыскания о пребывании здесь великого русского поэта М.Ю. Лермонтова. Им были сделаны рисунки и описана хата казака Мысника, где останавливался поэт. Эти исследования помогли музейщикам создать в 1976 году историко-этнографическую экспозицию музея М.Ю. Лермонтова в Тамани.
В марте 1880 г. император Александр II за особые труды наградил Е.Д. Фелицына орденом Станислава III степени. За свою плодотворную общественную деятельность он был избран почетным членом Ставропольского и Кубанского областных статистических комитетов, общества любителей изучения Кубанской области, действительным членом Московского археологического общества, Императорского общества любителей естествоиспытания, антропологии и этнографии, Императорского Одесского общества истории и древностей, Кавказского отдела Императорского русского географического общества, Таврической учетной архивной комиссии, Петербургского русского археологического общества, Общества любителей древней письменности.
После смерти Фелицына почти вся его библиотека, документы и фотографии, разошлись по частным коллекциям. И лишь в 1909 году, спустя 6 лет со дня смерти учёного, наказной атаман Михаил Бабыч издал указ о комплектовании личного архива историка и передаче его Войсковому музею.
