Это была последняя военная кампания незадачливого Куремсы. Однако победа над ним не принесла Даниле вожделенного спокойствия. В 1259 году на место Куремсы был назначен Бурундай, который обладал более подходящим для полководца складом характера. Это был исключительно проницательный человек, ничего не проходило мимо его внимательного взора. Его можно назвать жестким, но бессмысленная жестокость была не в его характере. Несмотря на то что Данило, понадеявшись на обещание папы организовать Крестовый поход, изрядно раздразнил татар, Бурундай решил сохранить его, ибо воинственность Данилы была ему по душе, и он имел на нее свои виды. Бурандай пришел на Волынь с огромным войском и послал Даниле лаконичное послание, в котором приказывал ему присоединиться к военному походу на Литву. Опасаясь явиться в стан Бурундая, Данило послал во главе войска своего брата Василька. Князь не хотел участвовать в литовском походе еще и потому, что рассчитывал восстановить союз с Миндовгом, несмотря на то что тот был в сильном гневе от того, что его людей потопили в озере возле Луцка. Татары не пытались покорить литовцев, они опустошали и сжигали их поселения, брали в плен детей и подростков, всех прочих убивали. Бурундай высоко оценил военные способности Василька и его демонстративную покорность татарам, а после того как отряд Василька привел в его стан множество пленных литовцев, прилюдно похвалил его, не преминув, однако, многозначительно заметить, что жаль, дескать, что брат его Данило не присоединился к походу. Однако Данило, поразмыслив, понял, что ему уже не удастся разыграть карту союза с Литвой, поэтому стоит воспользоваться тем, что она разорена татарами, и ослабить литовцев еще больше. Он самостоятельно предпринял поход на Волковыйск, захватил его и пленил князя Глеба, но тех, ради кого он пришел сюда, в городе не было. Даниле было не чуждо коварство: он хотел пленить своих недавних союзников Войшелка и Тевтивилла. И тогда он послал своих людей на розыски. Можно лишь предполагать, для чего ему были нужны эти знатные пленники, возможно, он собирался передать их Бурундаю в доказательство своей верности, а может, желал сохранить для будущих переговоров с Миндовгом. Но литовцы были неуловимы, более того, они выследили сына Данилы Романа и похитили его. Данило со своими воинами прошел все селения по берегу Зелвы, но сына не нашел. Посоветовавшись со своими военачальниками, он решил, что Войшелк и Тевтивилл нашли приют в городе Городен, и Роман, скорее всего, находится там же. Но Городен был укреплен, и в нем могло быть большое войско. Данило послал за другим своим сыном, Львом, и велел ему вести своих людей в город Мельник. Встретившись в Мельнике, они были вынуждены остаться в нем для того, чтоб дать отдых людям и лошадям – и те и другие были голодны и измучены. В это время в город прибыл посланник, который сообщил, что татары уже на землях ятвягов.
В это время татары уже шли в Мельник, намереваясь встретиться с Данилой. Но князь, отказавшись от осады Городена, спешно снялся и, отпустив брата и сыновей, ушел в Холм. А татары пошли в Дрогичин, не пожелав тратить силы и время на поиски Данилы.
За этими событиями последовал относительно спокойный 1261 год. Данило отстроил Холм практически в прежнем великолепии, особое внимание он уделял церквям. Вообще, князь Данило Галицкий, по всей видимости, был очень религиозным человеком. Известно, что он выстроил несколько храмов, не жалея средств на их отделку, и не начинал никакого дела, не помолившись перед святыми иконами. Однако его религиозность совмещалась с веротерпимостью, это давало ему большое преимущество как во взаимоотношениях с престолом св. Петра, так и с татарскими завоевателями. Ведь немало русских князей было убито во время их обязательного визита в Орду, потому что они не смогли скрыть своего презрения к идолопоклонству. Привычный же к соседству иноверцев, в частности литовских язычников, Данила смог вести себя дипломатично и не оскорбить чужой веры.
Пользуясь затишьем, Василько организовал брачный союз между своей дочерью Ольгой и черниговским князем Андреем Всеволодичем. По обычаю свадьбу играли в доме невесты во Владимире. Собралось множество гостей. Был там и Данило со своими сыновьями Львом и Шварном. В разгар веселья появились послы от Бурундая. Он был как всегда лаконичен: «Если вы мои союзники, встретьте меня. А кто меня не встретит, тот мой враг».