Среднее образование Миллер получил в пансионе Эннеса, после окончания которого в 1865 году поступил на историко-филологический факультет Московского университета. В университете он изучал историю народов Востока и восточный фольклор, греческий и латинский языки, санскрит. Первой научной работой Всеволода Федоровича стало студенческое зачетное сочинение «Восточные и западные родичи одной русской сказки», в котором он пытался исследовать причины схожести славянских и ряда восточных сказочных сюжетов. В 1876 году, после окончания университета, Миллер издал исследовательскую работу «Очерки арийской мифологии (Асвины-Диоскуры)» и защитил ее как магистерскую диссертацию. 

 
В своих исследованиях Миллер искал связующее звено между славянским индоевропейским и индоиранским фольклорными пластами. Именно так ученый заинтересовался историей и культурой народов Кавказа, в частности, осетин. Он совершил несколько этнографических поездок, по результатам которых издал два тома «Осетинских этюдов». Их ученый представил в качестве диссертации на степень доктора сравнительного языкознания. 

 
Третья часть «Осетинских этюдов» Миллера, удостоенная Большой золотой медали Императорского Русского географического общества, вышла в 1887 году. О своем труде автор писал: «Какая судьба загнала осетин в нынешние места их поселения, какое воспоминание сохранили они о своем прошлом. Каков склад их жизни, каковы их религиозные воззрения, какое место занимает их язык в группе иранских языков, каковы произведения осетинской поэзии — вот вопросы, на которые мы по возможности старались дать ответ». 

На рубеже ХIХ — ХХ веков Миллер открыл новый и плодотворный этап в истории российского академического кавказоведения. Его труды были посвящены важнейшим проблемам истории, археологии, этнографии, религии, эпиграфики, языкознания и устной народной поэзии народов Северного Кавказа. 

 
На протяжении тринадцати лет Миллер возглавлял Дашковский этнографический музей, который под его руководством вел основательную работу по сбору этнографического материала на Кавказе, в частности, в Осетии. Запасники музея пополнились многими предметами осетинского быта: утварью и мебелью, сукном и национальными костюмами, музыкальными и хозяйственными инструментами.

Миллер также сотрудничал с Московским археологическим обществом. Например, он организовал большую археологическую экспедицию по изучению башенных сооружений, могильников и склепов, средневековых церквей в Осетии. В ходе поездки он также записывал народные предания в Куртатинском, Алагирском и Дигорском ущельях и собирал материалы о религиозных верованиях осетин.