Решением Святейшего Патриарха Московского и всея Руси Алексия I (Симанского; †1970) и Священного Синода иеромонах Никодим направляется в Иерусалим в качестве заместителя Начальника Русской Духовной Миссии. Это послушание он выполнял на протяжении трёх лет — с февраля 1958 по февраль 1961 года.
«Святую Землю, — подчёркивает митрополит Никодим, — я считаю своей второй Духовной академией. Рядом со мной был мудрый наставник — начальник Русской Духовной Миссии архимандрит Никодим, который щедро делился со мной тем, чему нельзя научиться ни в каком учебном заведении — практическим опытом священнослужения не только на Родине, но и за её пределами. И кто знает, как бы сложилась моя духовная жизнь, если бы Десница Божия не свела меня с этим дивным иерархом Церкви Христовой, ревностным «служителем по домостроительству Божию» (Кол. 1, 25)».
15 ноября 1958 года по просьбе Святейшего Патриарха Московского и всея Руси Алексия I иеромонах Никодим возведён в сан архимандрита Блаженнейшим Патриархом Иерусалимским и всей Палестины Венедиктом (Пападопулос; †1980), и затем исполнял обязанности начальника Русской Духовной Миссии.
Тёплые отношения установились у архимандрита Никодима с иеромонахом Диодором (Каривалис; †2001), который с 1957 по 1962 годы нёс послушание архивариуса и библиотекаря в Патриархии. В 1981 году его избрали Блаженнейшим Патриархом Святого Града Иерусалима и всей Палестины. Здесь же зародилась многолетняя духовная дружба владыки с новоизбранным в сентябре 1958 года Святейшим Патриархом Сербским Германом (Джоричем; †1991).
В 1960 году отцом Никодимом закладывается основа храма в саду святой равноапостольной Марии Магдалины — в Магдале, на берегу Тивериадских вод, бывших свидетелями проповеди и чудес Христа-Спасителя.