Оказал Миллер помощь и приехавшему в середине июля 1921 года в Париж начальнику Штаба Русской Армии генералу П. Н. Шатилову. «В высшей степени воспитанный человек, большой эрудиции, скромный, спокойный, хорошо владеющий многими языками» (воспоминания Шатилова), Миллер сопровождал его при необходимых визитах. Начальник Штаба маршала Фоша генерал Вейган обещал содействие в сохранении в русских лагерях нужного пайка и в давлении на французские власти в Константинополе, чтобы они не препятствовали распоряжениям генерала Врангеля.
С конца 1921 года Врангель начал делать попытки к объединению вокруг армии широких политических сил и в связи с этим произвел кадровую перестановку в своем Штабе: его начальник генерал Шатилов был заменен генералом Миллером. Приказ об этом вышел 7 марта 1922 года. Шатилов был неспособен к ведению переговоров дипломатического характера, отличался излишней прямолинейностью и категоричностью, имел многочисленных недоброжелателей, в том числе среди союзников. Миллер же, напротив, пользовался широкими симпатиями французских военных кругов, «по настоянию которых якобы и [был] назначен Начштабом при Врангеле» (так считала чекистская агентура в Европе). Чекисты также указывали, что Миллер не считается в армии «ярым сторонником наступательных тенденций», хотя в других донесениях смену начальника Штаба связывали именно с тем, что «штаб Врангеля стал усиленно готовиться к весенним операциям». На деле же Миллеру приходилось больше заниматься сглаживанием различных конфликтов, как, например, в 1922 году – с правительством Болгарии, заподозрившим командование Русской Армии в подготовке государственного переворота. Принимал Миллер участие и в обсуждении вопроса об объединении «всех националистически, государственно мыслящих людей» вокруг Великого Князя Николая Николаевича.
15 мая 1923 года Евгений Карлович был, в соответствии с его личной просьбой, направлен к Великому Князю. Миллеру поручалось доложить о взглядах Врангеля на значение и характер будущего политического объединения. В полученной Миллером инструкции отмечалось, что после объединения Врангель предполагает остаться вне политики, с него должна быть снята всякая политическая, финансовая и другая работа, не связанная непосредственно с жизнью Армии.
Кроме того, Миллеру и Шатилову Врангель поручил вести переговоры с общественными и политическими организациями по созданию общего национального объединения заграницей. Но вскоре вокруг них как представителей Врангеля (Миллера – официального и Шатилова – негласного, в роли «доверенного лица») стали плестись интриги, что затрудняло их контакты с общественностью. Врангель был вынужден откровенно написать Миллеру: «Что же касается Шатилова, то убедительно прошу тебя… удержать его от участия в политической работе… Умный, отличный работник и горячо преданный нашему делу, он лишен качеств, необходимых для общественно-политической деятельности – тех самых качеств, которыми в полной мере обладаешь ты».
Но вскоре и деятельность Миллера, активно занявшегося координацией разведывательной работы, которая велась в различных странах, вызвала нарекания Главнокомандующего, считавшего ее чрезмерно самостоятельной. «Всю жизнь я привык нести ответственность за свои действия и никогда не подписывал имени моего внизу белого листа, хотя бы этот лист был в руках самого близкого мне человека», – писал Евгению Карловичу Врангель 29 июля 1923 года. 13 ноября в направленном Миллеру циркуляре Главнокомандующий требовал «размежевать работу и ответственность» (разведывательные и информационные функции должны были перейти к лицам, названным Великим Князем).