Одною из первых забот митрополита Феодосия была забота о епархии Новгородской. Новгородцы видимо тяготились своими отношениями к великому князю московскому, они предчувствовали, что не отстоять им против него своей вольности. Потому между ними бродила мысль – не лучше ли отделиться вовсе от Москвы и отдаться под покровительство литовского великого князя? А эта мысль неизбежно вела к другой: чтобы отделиться и от Московского митрополита и признать над собою власть митрополита Литовского. И вот, едва прошел месяц со времени вступления на кафедру митрополита Феодосия, как он счел нужным писать Новгородскому владыке Ионе: «Ты знаешь, сын мой, что в Литовскую землю пришел ученик Исидоров Григорий и что король его принял и дал ему престол Киевский. Если этот Григорий по каким-либо делам пришлет к тебе кого-либо из своих, то ты, помня свое обещание, данное при поставлении твоем и повторенное в твоих грамотах к великому князю и Собору русских епископов, не принимай и ни в чем не проси благословения от того Григория и не внимай его писаниям и поучениям. Да и детей твоих духовных в Новгороде и Пскове укрепляй твердо, чтобы они не принимали его благословения и поучения и не посылали к нему ни с чем, чтобы не поколебалась от ересей наша православная Церковь». Архиепископ Иона, муж святой жизни, умел вразумлять новгородцев и обуздывать их неприязнь к великому князю, а с другой стороны, умел заслужить любовь и уважение в Москве. Может быть, потому-то некоторые в Новгороде и были недовольны на своего владыку и нарушали его права. По крайней мере, не без причины сам Иона, когда посетил в 1463 г. Москву и здесь представился новому великому князю Иоанну Васильевичу III и митрополиту Феодосию, испросил у последнего грамоту для ограждения своих прав. Митрополит подтвердил всему духовному чину Новгородской епархии покоряться своему владыке, утвердил за ним все его земли, вотчины и пошлины, а новгородцам всем заповедал, чтобы они не вступались в те церковные пошлины и земли и не дерзали обижать Церковь Божию.
В то же время жители Пскова, враждуя на новгородцев, не помогавших им в борьбе с немцами, вздумали восстать и против Новгородского владыки, как это не раз случалось и прежде. В продолжение двух лет они не давали ему церковных пошлин и не дозволяли пользоваться церковными землями, водами и другими угодьями, находившимися в Псковской области, так что архиепископ Иона принужден был жаловаться митрополиту. Кроме того, к концу 1463 г. (12 декабря) они послали великому князю Иоанну Васильевичу грамоту, чтобы он повелел митрополиту поставить особого владыку в Пскове, и их брата псковитянина. Князь отвечал: «Это дело важное, мы внимательно порассудим с отцом нашим митрополитом; он созовет архиепископов и епископов, чтобы решить, можно ли тому быть». Через месяц с небольшим (22 генваря 1464 г.) псковичи повторили свою просьбу и прислали великому князю 50 рублей. Князь велел известить их, что он заботится о своей отчине – Пскове с отцом своим митрополитом и пришлет ответ чрез своих послов. Наконец ответ был получен и состоял в том, что нельзя быть в Пскове особому владыке, так как там искони не было епископской кафедры. Вдобавок митрополит прислал псковичам свою грамоту, в которой, упоминая о жалобе на них архиепископа Ионы, строго наказывал, чтобы они возвратили ему все отнятые земли и пошлины и впредь не обижали святой Софии новгородской и не вмешивались в ее отчины. Псковичи на этот раз покорились.