Жизнь Всеволодова в Венгрии, особенно в первое время, была очень тяжелой. В мае 1921 г. в Будапеште родилась дочь Татьяна. Всеволодов стал работать таксистом. А.А. фон Лампе писал о нем 31 января 1923 г. генералу А.П. Кутепову: «Еще до моего приезда в Будапешт, уполномоченным Красного Креста одна из немногих комнат в общежитии была предоставлена полковнику Генерального штаба Всеволодову. Я был также и в этой комнате и увидел в очень небольшом помещении самого полковника Всеволодова, его жену, троих детей и… автомобиль. Последний представляет собою единственное достояние этой семьи, куплен он при посредстве Земско-городского союза в Константинополе и постепенно оплачен, так как полковник Всеволодов — шофер. Ввиду необходимости для сборки машины теплого помещения, по-видимому, вся семья и получила комнату. Нечего и говорить, что помещение представляет собою мало завидного»[1130].
Одно из упоминаний о Всеволодове относится к концу 1926 г. В сводке № 9 о жизни союзов во II отделе РОВС к 1 декабря 1926 г., не предназначенной для печати, сообщалось о деятельности Союза русских офицеров в Королевстве Венгерском и отдела Общества галлиполийцев в Венгрии: «С грустью надо констатировать, что вся деятельность союзов неизбежно сводится к парированию нападений со стороны так называемых “законопослушных” монархистов (легитимистов. —
К середине 1930-х гг. Всеволодов нашел себя в другой сфере — организовал хор для озвучивания немого кино, а позднее создал свой балалаечный, а затем джазовый оркестр. В оркестре играли и двое сыновей Всеволодова — Борис и Юрий. Сам бывший командарм играл на рояле. С оркестром Всеволодов выступал в Италии. При этом ему повсеместно мерещились советские агенты, якобы разыскивавшие его по итогам Гражданской войны. Позднее в Венгрии Всеволодов с дочерью Татьяной создал джазовый дуэт.
В годы Второй мировой войны Всеволодов организовал магазин, в котором торговал чаем, кофе, фруктами, закусками. Из-за издержек этот бизнес пришлось закрыть. Всеволодов уехал в курортный городок Борсек в Карпатах, где вновь занялся музыкой. В конце войны Всеволодов попытался из Венгрии уехать в Швецию, но это не удалось.
В Венгрии Всеволодов дожил до конца Второй мировой войны. В октябре 1944 г. семья по стечению обстоятельств разделилась. Супруга Всеволодова, сын Николай с семьей и сын Юрий остались в Будапеште (удивительно, но Всеволодов даже не упомянул об их дальнейшей судьбе). Мемуарист с дочерью уехали в Шопрон к сыну Борису. Далее Всеволодов с дочерью отправились в Австрию. Затем им удалось уехать в Бразилию на пароходе, а оттуда в Парагвай, куда они прибыли 15 сентября 1948 г. В Парагвае их встретил русский генерал Н.Ф. Эрн. После нескольких лет жизни в Парагвае Всеволодов, видимо, в марте 1951 г. уехал в Аргентину. Работал на фабрике роялей, а позднее открыл свой кондитерский магазин. Впоследствии Всеволодов с дочерью уехал в США и поселился в Лос-Анджелесе, где около 1964 г. написал воспоминания.
О переезде в США Всеволодов вспоминал: «Мы закрыли магазин и уехали в другое государство. Здесь, в этой благословенной Богом стране, мы нашли все то, что мило и дорого нашему сердцу»[1132]. И далее: «Хотя мне исполнилось восемьдесят пять лет, но я не унываю, бодр, здоров и с большим желанием и энергией принялся за созидание новой жизни»[1133]. Продолжая апологию американской жизни, Всеволодов заключал, что в США «обеспечивают свободную и счастливую жизнь каждому гражданину. Здесь все предусмотрено до мельчайших деталей, и обыватель может жить, работать и творить уверенно и спокойно в противоположность гражданам Советского Союза, где нет никакой свободы и никто не знает, что с ним случится завтра»[1134]. Свои дни командарм окончил в Лос-Анджелесе 12 июля 1967 г. Похоронен он на кладбище Роуз Хилл Мемориал Парк[1135].