В этом походе участвовал подручный ему князь муромский Юрий. Кроме отдаленности и трудности пути, самые Болгары, очевидно, были в состоянии оказывать значительное сопротивление. Естественно поэтому, что набожный Андрей, не полагаясь на одну силу своей рати, прибегал к покровительству божественному. Он взял с собой в поход помянутую святыню, т. е. греческую икону Богородицы. Bо время главной битвы икона была поставлена под стягами, посреди русской пехоты. Битва окончилась полною победою. Князь Болгарский с остатком войска едва успел спастись в стольный, или Великий, город. Воротясь из погони за неприятелем, русские князья со своими дружинами совершили земные поклоны и благодарственное молебствие перед иконою. Затем они пошли далее, сожгли три неприятельских города и взяли четвертый, который летопись называет «славный Бряхимов».
Война, однако, не окончилась одним этим походом. Спустя восемь лет Андрей снова отправляет рать в ту же сторону; но сам нейдет, а поручает начальство сыну своему Мстиславу и воеводе Борису Жидиславичу, с которыми должны были соединиться сыновья подручных князей Муромского и Рязанского. Новый поход был предпринят зимой в неудобное время. Соединясь с муромцами и рязанцами, Мстислав две недели простоял на устье Оки, поджидая главную рать, которая медленно двигалась с Борисом Жидиславичем. Не дождавшись ее, князь с одной передовой дружиной вошел в Болгарскую землю, разрушил несколько сел и, захватив полон, пошел назад. Узнав о малочисленности его отряда, Болгары погнались за ним в числе 6000 человек. Мстислав едва успел уйти: неприятели были уже в двадцати верстах, когда он соединился с главной ратью. После чего войско русское воротилось домой, сильно потерпев от непогоды и всяких лишений. «Не годится зимою воевать Болгар» — замечает летопись по сему случаю.
Наряду с политической деятельностью Андрея замечательны также его заботы о делах церковных в своем княжении.
Начало христианства в том отдаленном краю положено было еще во времена Владимира и Ярослава. Но его утверждение встречало здесь те же или еще большие препятствия, чем в Новгородской земле, со стороны как русского, так и особенно финского населения. Летопись неоднократно повествует о мятежах, произведенных языческими волхвами, которым не раз удавалось возвращать к старой религии многих жителей, уже принявших крещение. При утверждении греческой иерархии на Руси Суздальская земля не вдруг составила самостоятельную епархию. Будучи отнесена к Переяславскому уделу, она иногда управлялась переяславскими епископами, а иногда имела своих особых архиереев, которые пребывали в старейшем ее городе Ростове. Положение этих ростовских иерархов первое время было особенно трудное, потому что они не имели такой опоры в князьях и дружине, как другие епископы. Князья еще не жили сами в той земле; а приезжали сюда только временно и управляли ею посредством своих наместников. Из первых ростовских епископов особенно славны своею просветительною деятельностью св. Леонтий и преемник его Исаия, оба постриженники Киево-Печерской лавры, подвизавшиеся на север в последней четверти XI века.
Житие Леонтия повествует, что он был изгнан из Ростова упорными язычниками и некоторое время жил в окрестностях его, собирая вокруг себя детей, которых привлекал ласками, научал христианской вере и крестил. Потом он воротился в город и продолжал здесь апостольские подвиги, пока не принял мученического венца от мятежных язычников. Его подвиги и кончина, очевидно, относятся к той эпохе, когда на севере происходили народные возмущения от языческих волхвов, по примеру тех, которых встретил на Белоозере воевода Ян Вышатич. Следующий за ним епископ Исаия, по словам его жития, ходил по Суздальской земле со своею проповедью, укреплял веру вновь крещенных, обращал язычников, сожигал их требища и строил христианские храмы. Ему помогал Владимир Мономах во время своих поездок в Ростовскую землю. В одно время с Исаией подвизался и третий святильник Ростовского края, св. Авраамий, который сам был уроженцем этого края. Он является основателем иноческого жития на северо-востоке, и в этом отношении походит на первых киево-печерских подвижников. Подобно им, он с юных лет чувствовал склонность к благочестию и уединению, удалился из родительского дома на лесистый берег озера Неро и поставил себе здесь келию. В Ростове жители «Чудского конца» еще поклонялись стоявшему за городом каменному идолу Белеса и приносили ему жертвы. Авраамий жезлом своим разрушил этот идол; а на месте его основал первый Ростовский монастырь в честь Богоявления. Подобно Леонтию он привлекал к себе юношей, учил их грамоте и крестил; потом многие из них приняли пострижение в его монастыре. Язычники не раз хотели напасть на него и сжечь монастырь; но преподобный не смущался их угрозами и энергично продолжал свою проповедь.