В 1154 году отец Андрея, князь Ростовский и Суздальский Юрий Долгорукий стал великим князем Киевским. Раздавая сыновьям уделы, он отдал Андрею Вышгород (к северу от Киева), в котором тот уже княжил однажды (за пять лет до того), но не долго. Не было суждено Андрею задержаться там и в этот раз. Сохранялась в храме женского монастыря в Вышгороде чудотворная икона Богородицы, привезенная из Царьграда и писанная самим евангелистом Лукой. Н.И. Костомаров писал: «Рассказывали о ней чудеса, говорили, между прочим, что, будучи поставлена у стены, она ночью сама отходила от стены и становилась посреди церкви, показывая как будто вид, что желает уйти в другое место». Андрей Юрьевич, узнав об этом чуде, однажды летней ночью 1155 года, с помощью священника и диакона этого монастыря, вынес икону из храма и в ту же ночь, с иконой в руках, двинулся из Вышгорода на север, в Ростов. Князь намеревался эту икону, как писал Костомаров, «перенести в суздальскую землю, даровать таким образом этой земле святыню, уважаемую на Руси, и тем показать, что над этою землею почиет особое благословение Божие». Князь сделал это тайно, без отчего благословения и согласия вышгородцев, «повинуясь лишь воле Божией». И на всем пути от Вышгорода икона являла ему и его спутникам свою чудотворную силу, описанную впоследствии в «Сказании о чудесах Владимирской иконы Божией Матери».
Ночью, в десяти верстах от Владимира, кони вдруг сами остановились, а князю во сне явилась Богородица и приказала ему: «не хочу, чтобы образ Мой несли в Ростов, но во Владимире поставь его, а на сем месте во имя Моего Рождества церковь каменную воздвигни». В память об этом чуде Андрей повелел иконописцам написать икону Божией Матери такой, как Пречистая явилась ему. Икона, названная Боголюбской, прославилась впоследствии многочисленными чудотворениями. На указанном Богородицей месте князь Андрей построил храм Рождества Богородицы (в 1159 году) и заложил город