Владимир Петрович родился в 1852 г. в Калуге в старинной дворянской семье, связанной с традицией военной службы в России. По воспоминаниям Наливкина, уже в шести-семилетнем возрасте он жадно слушал рассказы отца, заслуженного ветерана-кавказца, о сражениях с турками и «непокорными горцами». Таким образом, выбор Владимиром Петровичем военной стези был закономерным итогом полученного им домашнего воспитания. По окончании военной гимназии Наливкин в 1870 г. поступил в Павловское военное училище. Уже в годы учебы Владимир Петрович проявил замечательные лингвистические способности, овладев в совершенстве французским языком. Выпуск из училища в 1872 г. «по первому разряду» давал молодому офицеру право вступить в гвардию, но «неудержимое желание понюхать пороху» заставило Наливкина избрать службу в Туркестане.
К этому времени существовавшие русские владения в Средней Азии были объединены в образованное в 1867 г. Туркестанское генерал-губернаторство. Его администрация, в отличие от других районов империи, подчинялась в Петербурге не Министерству внутренних дел, а Военному министерству. Туркестанкий генерал-губернатор одновременно являлся командующим войсками Туркестанского военного округа. Представители общеимперских ведомств (иностранных дел, финансов, народного просвещения и др.) входили в особый совет при начальнике края и обязаны были согласовывать с ним свою деятельность. Генерал-губернатору подчинялись военные губернаторы областей края. Последние ведали областными правлениями, начальниками уездов (назначавшимися из числа русских офицеров и чиновников) и «туземной» администрацией, формируемой из представителей коренного населения, продолжавшего жить по законам адата и шариата. В первые годы пребывания Наливкина в Средней Азии тут действовал целый ряд «Временных правил» и «положений» по управлению покоряемыми одна за другой территориями Туркестана. На смену им в 1886 г. пришло единое «Положение об управлении Туркестанского края», регламентировавшее основные начала судебной системы, систем землевладения и землепользования, налогообложения, административно-политического устройства и др.
В первые годы своей службы в Туркестане Наливкин принимал активное участие в боевых действиях, за Хивинский 1873 г. и за Кокандский 1875 г. походы он был награжден орденами и внеочередным чинопроизводством. В то же время в воззрениях Владимира Петровича происходит серьезный перелом. Он глубоко разочаровался в военных способах реализации среднеазиатской политики империи и решил уйти из действующей армии. С 1876 г. Наливкин служил в системе гражданского (т. н. военно-народного) управления, где занимал должность помощника начальника Наманганского уезда Ферганской области, а затем в 1878 г. вообще вышел в отставку. К этому моменту он пришел к выводу о том, что для «введения основ русской гражданственности» среди местного населения русским людям надо прежде всего как следует познакомиться «с этим населением, с его языком, бытом и нуждами».
Именно поэтому Наливкин и его молодая жена, выпускница Саратовского женского института Мария Владимировна (урожденная Сарторий) приняли абсолютно неожиданное для их русского окружения решение. Супруги Наливкины поселились в кишлаке Нанай Наманганского уезда, где они могли непрерывно познавать «язык, земельный быт, религию и обычаи» коренного оседлого и кочевого населения «не по книжным источникам, а из самых источников народных».
Шесть лет жизни в подобных, достаточно трудных для европейцев условиях привели к блестящим научным результатам. Приобретенные обширные знания языков, быта и нравов ферганских узбеков, киргизов и таджиков позволили Наливкину составить и издать многочисленные пособия, словари и хрестоматии, имевшие целью облегчить изучение тюркских языков в России. Им была создана первая в русской и европейской науке, до сих пор сохраняющая свою познавательную ценность «Краткая история Кокандского ханства» (Казань, 1886). Тогда же и там же в свет вышло, пожалуй, наиболее выдающееся совместное научное произведение супругов Наливкиных – книга «Очерк быта женщины оседлого туземного населения Ферганы». Мария Владимировна Наливкина стала первой европейской женщиной-исследователем, попавшей на недоступную для посторонних мужчин женскую половину жилища коренных обитателей Средней Азии, где смогла увидеть и затем совместно с Владимиром Петровичем обобщить уникальнейшую этнографическую информацию. Содержание их совместного труда по сути своей гораздо шире его конкретного названия: Наливкины создали непреходящее по своей научной значимости фундаментальное исследование, раскрывающее самые различные стороны жизни и женского, и мужского коренного населения Туркестана. Данная работа супругов Наливкиных была высоко оценена русской научной общественностью, авторы ее были удостоены одной из самых почетных наград того времени – Большой золотой медали Русского географического общества.