Из внешних действий Андреевых во все это время примечательна только война против волжских болгар, сильных и богатых его соседей с юго-восточной стороны (1164). Желая ли обезопасить себя с их стороны и внушить страх от русского имени, которое здесь давно не было слышно, или вследствие какой-нибудь распри и за добычей, Андрей с сыном Изяславом и муромским князем, взяв с собой чудотворный образ, отправился за Оку и Волгу. Перед сражением он приобщился Святых Тайн и обратился с молитвой к своей Божественной Помощнице. Вслед за князем и все воины ударили челом перед иконой, и, облобызав ее, смело пошли против врагов. Болгары были разбиты, и великий князь Андрей с конными далеко преследовал их. Пешие остались на полчище под знаменами, около Божией Матери. Князья, вернувшись, пали ниц перед ней, хвалу воздавая со слезами и радостью великой. Андрей взял еще три города, и, наконец, столицу Болгарскую, на берегах Волги, знаменитый Бряхимов, обширные развалины которого мы теперь видим верстах уже в двадцати от реки. С богатой добычей и славой возвратился великий князь суздальский в отчизну и уставил праздновать своей Покровительнице, в благодарное воспоминание о счастливом походе, 1 августа, что совершается православной церковью и до сих пор.
В делах южной Руси Андрей не принимал во все это время никакого участия, если только мы исключим малую помощь, посланную им в 1160 году, с сыном Изяславом, по просьбе союзника его Изяслава Давыдовича, для его племянника, князя вщижского, Святослава Владимировича, за которого выдал свою свою. Но он готовился к действиям.
Соседние князья, рязанские, муромские, смоленские, полоцкие, так или иначе, признали над собой волю Андрея, и во всех следующих его предприятиях находились в числе его воинов.
Первым предметом его замыслов был Новгород, богатое и сильное, не подверженное разделению и междоусобиям, цветущее торговлей княжество, с которого он не спускал глаз с самого своего водворения во Владимире.
Андрей еще тогда (1160) послал сказать новгородцам: «Ведомо вам буди, что я хочу искать Новагорода добром или лихом; целуйте мне крест на том, чтоб иметь меня отцом себе, а мне желать вам добра». «С тех пор, замечает летописец, начали новгородцы мястися и часто творить веча». Почуяло их сердце, что заходит на них от близкого Владимира туча, какой не видывали они еще от далекой Киевской Руси, и что придется им когда-то потерять свою дорогую волю. Андрей, сказав это слово, сделал первый шаг к Новгороду, проложив дорогу, по которой неукоснительно пошли его преемники, князья владимирские, а затем московские, и с которой Ивану Третьему осталось ступить только один шаг, уже последний, до Святой Софии.
В следующем году, чтобы умилостивить Андрея, новгородцы прислали просить у него сына. Сына он почему-то не давал, а предлагал брата, от которого те отказывались, ибо он уже княжил у них и не угодил им; тогда он дал племянника Мстислава Ростиславича, разумеется, на условиях, на каких хотел, или, как говорилось тогда, «на всей воле своей» (1160).
Но вскоре переменил свое решение и вывел племянника из Новгорода, договорившись со своим старшим двоюродным братом, великим князем киевским, Ростиславом Мстиславичем, который прислал туда своего сына Святослава, не без особых выгод для Андрея, уступая ему, кажется, Двинскую дань (1161).
Святослав жил у них долго, но, наконец, они рассорились. Новгородцы, по старой привычке, указали ему путь от себя, поцеловав Святую Богородицу, «яко не хотети его». Андрей заступился за Святослава, как за своего союзника, и отправил к нему помощь на Волгу, куда тот удалился. Изгнанный князь сжег Новый Торг, а прочие союзники, смольняне и полочане, по воле князя Андрея, Великие Луки.
Они ходили было к Русе, но, не дойдя, вернулись, когда услышали о приготовленной встрече (1167). Новгородцы избрали к себе на стол сына великого князя киевского Мстислава Изяславича, Романа. Союзники перехватили послов и заняли все пути, чтобы до него не могло дойти никакой вести о происходившем. Андрей, «силою местяче» (насильно помещая) на стол новгородский своего ставленника, говорил новгородцам: «Нет вам другого князя, кроме Святослава», и новгородцы, не привыкшие к такому языку, возмутились, убили посадника и других чиновников, державших сторону изгнанного князя, и настаивали на своем выборе. Новые послы, с Даньславом Лазутиничем, успели пробраться окольными дорогами, мимо всех засад, в Киев, и привезли, наконец, князя, которого новгородцы ожидали от Семена дня до Велика, сидя с одним посадником Якуном (1168). Новгородцы обрадовались, но Андрей вознегодовал на них за упорство и ослушание, вознегодовал еще более на киевского Мстислава, как тот осмелился, вопреки ему, дать сына строптивому городу.
Он решил наказать и Мстислава, и Новгород, и начать с первого, которого не любил издавна. Ему досадно было, что этот младший князь, хотя и по условию со старшими, занял великое княжество Киевское, к которому сам он, Андрей, по праву был ближе сына Изяславова. Прочие русские князья также завидовали ему, начали сноситься речами на него с Андреем и утвердились крестом между собой.