После испытания в воинском мастерстве и представления царю, Менезис был направлен на службу в Смоленск в должности капитана пехотного полка. Вскоре он получил и майорское звание. В Москве Менезис женился на немке (имя ее не известно) из Немецкой слободы. Семья вместе с ним переехала в Смоленск.
Во время своей службы в Смоленске Менезис сдружился со стрелецким полковником Кириллом Полуэктовичем Нарышкиным, будущим тестем царя Алексея Михайловича, Сблизился Менезис с Нарышкиным и в силу того, что брат Кирилла, Федор Полуэктович, был женат на Евдокии Петровне Гамильтон, шотландке по происхождению, принявшей православие, Эти Гамильтоны приходились родственниками Менезису. На другой Гамильтон, Евдокии Григорьевне, был женат любимец царя Артамон Сергеевич Матвеев, глава Посольского приказа, рейтарский полковник и воспитатель Натальи Кирилловны, будущей царицы. Эта дружба и причудливые родственные связи способствовали тому, что впоследствии Менезис стараниями своих друзей и родственников был приближен к царю.
В 1667 Менезис был послан в Швецию для найма горнорабочих. С поручением он справился, как видно, хорошо, чем и обратил на себя внимание. В 1671 году он выехал в Англию по случаю смерти своего отца. Посольский приказ, уже имевший возможность проверить деловые качества Менезиса в Швеции, на этот раз поручил ему сбор сведений о политических делах в Европе. Сохранившийся «опрос» Менезиса, который был произведен после его возвращения и на который он дал обстоятельные ответы, свидетельствует о том, что он и на этот раз весьма удачно справился с поручением. В скором времени Менезису представилась возможность участвовать и в более серьезных дипломатических делах.
В июле 1672 года огромная турецкая армия султана Магомета IV перешла Дунай и вторглась в пределы Польши. Уже в скором времени была взята крепость Каменец-Подольский, что открывало туркам путь не только на Львов и Варшаву, но и на Киев. Россия стала перед реальной угрозой кровавого османского нашествия.
Царь Алексей Михайлович, сознавая военную слабость России, решил обратиться к европейским государствам, надеясь найти среди них союзников и получить необходимую военную помощь. Менезис, как человек грамотный и опытный, хорошо знавший многие европейские языки и имевший уже некоторые навыки общения с высокопоставленными государственными лицами, был срочно вызван в Москву и направлен в качестве посланника в Берлин, Дрезден, Вену, Венецию и Рим. Ему поручалось вручение грамот курфюрсту, цесарю, дожу и папе римскому от царя Алексея Михайловича с призывом составить антитурецкую коалицию.
Поездка Менезиса продолжалась с 20 сентября 1672 по 28 марта 1674 г. Хотя, как считают историки, его миссия не была удачной, все же по возвращению