Некоторое время он был игуменом на острове Кяфе, затем жил у валахского воеводы Матвея и молдавского Василия. Прожив у последнего два года, Арсений отправился в Киевскую академию, которая пользовалась тогда громкой славой в качестве духовно-просветительского центра Юго-Западной Руси, надеясь получить преподавательское место, но по пути узнал, что туда не принимают без разрешения польского короля. Тогда он поехал в Варшаву. Здесь он был принят королём Владиславом IV и даже будто бы излечил его от каменной болезни, за что получил грамоту к киевскому митрополиту Сильвестру Коссову. В Киеве состоялось его знакомство с патриархом Иерусалимским Паисием, которому он очень понравился своим умом и разносторонним образованием. Патриарх взял Арсения в Москву и на время своего пребывания там зачислил в штат своей патриаршей свиты в качестве «патриаршего уставщика».
После отъезда Паисия из Москвы Арсений Грек остался здесь по приглашению царя Алексея Михайловича, «яко многим языком искусный», и даже занялся учительством. Однако вскоре его педагогическая деятельность неожиданно прервалась. На обратном пути через Киев и Валахию патриарх Паисий якобы узнал от местного населения такие нелестные для репутации Арсения отзывы, что счёл своим долгом с дороги сообщить об этом в Москву. «Еще да будет ведомо тебе, благочестивый царь, про Арсения, — доносил патриарх со слов малороссов и валахов, — что он… прежде был иноком и священником и сделался басурманом; потом бежал к ляхам и у них обратился в униата, — способен на всякое злое безделие: испытайте его добре и все это найдете…»
Получив донесение патриарха, царь велел князю Н.И. Одоевскому и думному дьяку М. Волошенинову провести допрос Арсения. Тот во всём запирался: «Католического сакрамента в Риме не принимал и не только в басурманстве, но и в униатстве не был». Однако когда князь Одоевский пригрозил телесным осмотром, Арсений сознался, что он действительно был обасурманен, то есть обрезан и обращён в ислам, неволею, но впоследствии принёс покаяние янинскому митрополиту и был им помазан миром. На следствии Арсения сравнили с «волком в овечьей шкуре». Суд приговорил сослать его на Соловки. Здесь он неожиданно возлюбил «русское благочестие», в течение трёх лет всячески старался расположить в свою пользу местных иноков, расхваливая русские обычаи и истово крестясь двуперстием. В результате соловецкие иноки отозвались о нём весьма одобрительно.
В 1652 году Никон, приехавший за мощами митрополита Филиппа на Соловки, освободит Арсения и возьмёт его с собой в Москву, где отведёт ему келью в собственном доме, поручит заведование патриаршей библиотекой и с 1654 года назначит справщиком Печатного двора и переводчиком богослужебных книг. Но недальновидный Никон пригрел на груди змею. Когда он потеряет власть и более уже не сможет с прежней щедростью оказывать Арсению свои милости, тот предаст его и, не задумываясь, перейдёт на сторону врагов бывшего патриарха.