Указ о прощении Артамона Матвеева последовал во время приготовлений к новой свадьбе царя Федора Алексеевича в декабре 1681 года. Долгожданные новости об освобождении из ссылки привез на Мезень капитан Стремянного полка Иван Сергеевич Лешуков «генваря в первых числах» 1682 года (у Лешукова было еще одно поручение в Пустозерске, где им был проведен розыск по делу вскоре казненного протопопа Аввакума). «Реабилитация» боярина Артамона Сергеевича Матвеева была полной; в указе признавалось, что он стал жертвой клеветы, ему возвращали боярский чин и отнятое имущество — «Московской их двор, и подмосковныя и другие вотчины и пожитки» (насколько могли после состоявшихся «раздач» и «продаж»). Боярина Артамона Матвеева переводили в Лух, где он должен был дожидаться нового царского указа. Несколько верст от Мезени, снабдив бывших ссыльных «подводами и напутными потребами», боярина и его свиту провожал их бывший пристав Гаврила Тухачевский «с великим почтением» и сожалениями от разлуки (
Дорога от Мезени до Луха лежала через Холмогоры, где Артамон Матвеев сразу вспомнил о привилегиях своего боярского чина. Все теперь стремились представиться Матвееву и чем-либо угодить ему, чтобы тот не забыл их услуги. Первым на пути, кто встретил бывших ссыльных «с великою любовью и открытством приятельским всего дому своего», стал двинской воевода боярин князь Никита Семенович Урусов. Не отставали от воеводы «и все Колмогорские жители, иноземцы и всякаго чину люди».
Холмогоры тоже были местом ссылки, и там хорошо понимали страдания опальных. А вот по поводу холмогорского воеводы, хотя и продемонстрировавшего свое радушие, всё же не стоило обольщаться. Клан братьев князей Урусовых, служивших при дворе в высоких чинах, был большим и разветвленным. В свое время князья Урусовы много потеряли от нового брака царя с Натальей Нарышкиной и изведали опалу. Один из братьев князей Урусовых, Петр Семенович Урусов, был женат на родной сестре боярыни Морозовой Евдокии Урусовой, погибшей вместе с ней за старую веру в боровской тюрьме. Свое положение при дворе князь Петр Урусов предпочел поддержке жены, отказавшись от нее. Потом братья князья Урусовы снова вошли в близкое окружение царя Федора Алексеевича и даже стали его свойственниками по царице Агафье Грушецкой. И вот боярин князь Никита Семенович Урусов (на которого местные жители безуспешно жаловались царю Федору Алексеевичу в корыстолюбии) первым встречал и провожал «пять верст от Колмогор, до села, зовомого Матигоры» боярина Матвеева.
Дальнейший «зимний путь» лежал по хорошо известному тракту, связанному с торговлей через Архангельский порт. В Шенкурске у боярина Артамона Матвеева состоялась встреча с еще одним хорошо ему известным думным дьяком, а потом думным дворянином Григорием Степановичем Карауловым. Его шенкурское воеводство было явной опалой, так как еще недавно думный дворянин Караулов входил в Расправную палату, занимавшуюся разбором важных дел с участием избранных членов Думы. Как и в Холмогорах, у боярина Матвеева и его сына осталось самое лучшее впечатление от встречи их шенкурским воеводой «с великою честию».
По мере движения матвеевского «поезда» с Севера на Волгу почетные встречи происходили в каждом крупном городе — Вологде, Ярославле. Вологодский воевода стольник князь Петр Иванович Львов хотя и был из тех самых обиженных Матвеевым князей Львовых (родной брат Семена Ивановича Львова, чьи вотчины оказались у Матвеева), выехал вместе с детьми встречать боярина Артамона Сергеевича Матвеева за несколько верст от города. Повторились и приемы разных лиц, среди которых упомянуты «иноземцы» Иван Гаутман, Володимер Эводс, Андрей Буш «