В 1945 г. Всеволод Рошко все–таки попал в «Руссикум», и в следующем году его рукоположили в священный сан. Дальнейшие годы его жизни во многом типичны для священников «русской миссии» в эмиграции. Будучи студентом «Руссикума», он работал в лагерях для интернированных русских в Италии. В 1948–м его направили в Аргентину к о. Филиппу де Режису для пастырской работы в русском католическом приходе в Буэнос–Айресе. Оттуда путь о. Всеволода лежал в Чили, но в 1952–м он вновь оказался в Париже. Видимо, уже тогда у него начали формироваться определенные аскетические настроения, и на некоторое время он присоединился к монашеской общине «Малых братьев Иисуса» в пустыне Северной Африки. Но подорванное тяжелой болезнью здоровье не позволило ему долго оставаться в суровых условиях пустыни.
Отчасти под влиянием своих бесед с братом о положении православных на Аляске о. Всеволод, получив разрешение из Рима, перебрался на далекий остров Диомида (США), расположенный в непосредственной близости от советской границы. Избранный им аскетический образ жизни приходилось сочетать с пастырскими обязанностями, поскольку местное православное население подолгу оставалось без пастырской опеки. О. Всеволод построил небольшую часовню и домик при ней. Постоянным его призванием на этой земле вблизи советских рубежей была молитва за Россию. Но вскоре американские военные власти дали понять, что его присутствие в пограничной зоне нежелательно, и о. Всеволоду пришлось перебраться на материк. На Аляске он провел в общей сложности около десяти лет, пока нелегкий для его слабого здоровья уклад жизни не вынудил его уехать.
В 1968 г. о. Всеволод переехал в Иерусалим для миссионерской работы в недавно открытом там по инициативе папы Павла VI «Доме для бедных паломников», более известном как «Дом Авраама». В Святых местах он провел последние восемнадцать лет своей жизни. Его служение России продолжилось в общении с многочисленными эмигрантами из Советского Союза, выехавшими в Израиль, и православными священниками на Святой Земле.
Удивительная открытость людям, действительно вселенское церковное мировоззрение, простота, внимание к человеческим нуждам делали о. Всеволода фигурой по–своему уникальной в Иерусалиме — для него практически не было недоступных мест в этом многоязыком и многоконфессиональном городе. Замечательное тому свидетельство прозвучало в надгробном слове о. Всеволоду, сказанном русским православным священником о. Ильей Шмаином: «Потому он объединял всех и снимал все противоречия, разъединяющие нас, что был всегда готов всей душой откликнуться на любой призыв, помочь всем, чем только мог, и через силу, каждому человеку, которого он встречал, будь он русский или еврей, мусульманин или христианин, католик или православный, приверженец Синодальной Церкви или Московской Патриархии. Это горение души, пламень истинной Христовой любви и освещал и собирал вокруг него всех, кто знал отца Всеволода. Это и делало его таким исключительным. Ведь отец Всеволод был единственным человеком в Иерусалиме, а значит — и во всем мире, которого можно было увидеть в один день и в католическом монастыре, и в греческой патриархии, и на невеяковской кухне у неверующего еврея–художника, — и всюду ему были рады. Он даже обладал — при всей его нищете, непрактичности, слабости — неким могуществом благодаря способности всех объединять, всем быть нужным».
Постоянный интерес к России открыл для него в общении с эмигрантами из СССР имя о. Александра Меня; о. Всеволод вступил с ним в переписку. Общение этих двух выдающихся людей нуждается в более подробном и компетентном изложении, хотя частичная попытка уже была предпринята в публикации о. Ильи Шмаина (Вестник РХД № 165).
О. Всеволод оказал значительную помощь в библейских исследованиях о. Александра, знакомя его с современными западными экзегетами, внося различные замечания в его работы и подыскивая для него нужную литературу. Дважды о. Всеволоду удалось побывать в России — в конце 1970–х и начале 1980–х годов, и всегда ему помогал в общении с православными священниками искренний и чуткий интерес к жизни Православной Церкви.