Большая часть чехословацкой службы Всеволода проходила в частях горной артиллерии: с октября 1926 г. – в 252-м (Домажлица), а с 30 сентября 1928 г. – в 260-м дивизионах (Банска-Штьявница). С 15 января 1938 г. он служил в рядах развернутого на базе последнего 15-го артполка в Топольчанах. В разное время занимал должности командира взвода, аудитора батареи, первого офицера батареи, командира полевой и запасной батарей, командира подофицерской школы, заместителя командира дивизиона и первого помощника командующего полка. Кроме того, с 1 июля до 24 августа 1928 г. он был прикомандирован к 6-му пограничному батальону «Сибирских ударников» в качестве командира 1-й артиллерийской батареи. Русский офицер трижды повышался в звании: 2 декабря 1926 г. до капитана, 1 октября 1928 г. – до штабного капитана и, наконец, 1 января 1937 г. – до майора. Неизменно заслуживая образцовые отзывы командования, он дважды проходил дополнительное обучение: в 1926 г. – курс артиллерийской школы в Оломоуце и в 1935 г. – курс пассивной обороны против авиации. Во время мобилизации 1938 г. Милоданович, командовавший запасным дивизионом 15-го полка, принял под свое командование гарнизон Тополчан[6].
Впоследствии Всеволод вспоминал о своих новых сослуживцах и, зачастую, недавних противниках – бывших австро-венгерских офицерах, сравнив их с военнослужащими российской армии:
Его дочь Татьяна вспоминает эпизод, связанный со службой отца:
Службу в вооруженных силах Словакии Милоданович начал с момента их создания, 30 марта 1939 г. приняв командование 15-м артполком, но официально в их ряды с сохранением звания майора он был зачислен лишь 14 апреля. При первой реорганизации армии, 1 мая того же года, русский офицер был назначен на должность командира II дивизиона 4-го артиллерийского полка в Спишска-Нова-Вес, а в сентябре, во время войны с Польшей, кроме того, командовал гарнизоном в Спишска-Нова-Вес и Кежмароке. При новой реорганизации армии Всеволод с 15 ноября 1939 г. оказался в рядах 3-го артиллерийского полка, 15 января приняв под командование его I дивизион, дислоцировавшийся в Чемерне, а 30 сентября 1940 г. последовал перевод на должность командира II дивизиона 2-го артполка (размещавшегося отдельно от остальных сил части, в Прешове).
После начала войны между Словакией и СССР, 26 июня 1941 г., дивизион Милодановича вместе со всей армией был отправлен на фронт[9], где нес оккупационную службу, размещаясь в селе Солоньске восточнее западно-украинского Дрогобича, но уже 20 августа снова вернулся к месту постоянной дислокации. С 23 сентября до 22 ноября Всеволод командовал 2-м артполком, вернувшись затем на свою прежнюю должность. С 7 мая 1942 г. он снова замещал командира полка, но уже 1 июня был отправлен на Восточный фронт на должность командира II дивизиона 31-го артиллерийского полка Быстрой дивизии, в составе которой участвовал в ожесточенных боях на туапсинском направлении[10].