Опасаясь неизбежных ответных действий русских воевод, в особенности страшившей их зимней войны, литовские власти уже в сентябре 1535 г. обращаются к Москве с предложением начать мирные переговоры. Действовали они осторожно, зондируя почву через пленного воеводу князя Ф. В. Овчину Оболенского, чей двоюродный брат Иван Федорович Овчина Телепнев-Оболенский занял выдающееся положение при дворе вдовствующей великой княгини Елены Васильевны Глинской, правительницы Московского государства. Начавшиеся вскоре переговоры с определенными трудностями, но продвигались вперед.
Воспользовавшись наступившей в военных действиях паузой, литовцы, решили ликвидировать опасное для них изменение линии границы по псковскому рубежу, где в июле 1535 г. была выстроена новая русская крепость Ивангород (Себеж). 27 февраля 1536 г. 20-тысячное войско киевского воеводы Андрея Немировича и полоцкого воеводы Яна Глебовича осадило Себеж. Русские устроили вылазку и, оттеснив часть литовского отряда на лед озера, уничтожили. Победители захватили богатые трофеи, в том числе знамена и «варганы» (по-видимому, сигнальные музыкальные инструменты) После поражения литовское войско сняло осаду и поспешно отошло от города. Во время боев под Себежем «из сороковые пищали» был убит один из литовских воевод «пан Воитек Николаев». В честь победы Елена Глинская велела заложить в Себеже церковь Живоначальной Троицы.
Несмотря на достигнутый в боях за Себеж успех, московская сторона, озабоченная угрозой нападения со стороны Казани и Крыма, не могла перейти к активным наступательным действиям. Значительная часть русского войска уже зимой 1535/36 г. (сбор войск был закончен 20 февраля 1536 г.) была сосредоточена в Нижнем Новгороде, чтобы действовать против казанских татар, отряды которых доходили «от [этого] города за 10 верст».
Тем не менее, определенная активность русских сил отмечалась и на западных границах. Так, в январе 1536 г. «велел князь великий поставити во Ржевском [уезде] на Литовском рубежи град землян, а нарек его Заволочие». Весной этого же года на прежнем месте восстанавливается разрушенный литовцами и поляками в 1535 г. «град Стародуб», а 19 апреля начинается строительство в Торопецком уезде крепости Велиж, законченое в июле 1536 г. Тогда же из отстроенного Стародуба ходил с войском в поход на Любеч воевода князь Иван Васильевич Горенский, а под Витебск выступили полки князя Ивана Ивановича Барбошина. Опустошив окрестности этих городов, воеводы вернулись на свою территорию.
Расчет литовских властей на быструю и победоносную войну не оправдался. Королевская казна была пуста, посполитое рушение собиралось плохо. Учитывая эти обстоятельства, Сигизмунд I принял трудное решение завершить затянувшуюся войну. В июле 1536 г. он прислал в Москву своего личного посланника кревского наместника Никодима Яновича Тихоновского, привезшего опасные грамоты для русских великих послов. В качестве ответного шага бояре отправили в Вильну своего посланника — сына боярского Тимофея Константиновича Хлуденева, с опасными грамотами для литовских великих послов. Король и его советники уступили первыми, и в ноябре 1536 г. Т. К. Хлуденев вернулся с сообщением о прибытии в Москву к Рождеству литовских великих послов полоцкого воеводы Яна Глебовича, витебского воеводы Матвея Яновича и писаря Венцеслава. Посольство несколько задержалось и вступило в русскую столицу 12 января 1537 г.
На начавшихся тогда в Москве мирных переговорах литовская сторона потребовала передачи Вильне Новгорода и Пскова, а также включения в условия мира статей старого докончания, заключенного еще в 1449 г. Василием II и Казимиром IV. Русская сторона выдвинула к Литве свои контрпретензии, требуя возвращения не только захваченного в ходе последней войны Гомеля, но и Киева, Полоцка, Витебска. Уступать в решении принципиальных вопросов стороны не захотели и, как обычно заключили перемирие. Оно было подписано 18 февраля 1537 г. сроком на 5 лет и вступало в силу 25 марта этого же года. Согласно статьям Московского перемирия 1537 г., Гомель и гомельские волости отошли к Литве; города Себеж и Заволочье, а также Долысская волость — к Московскому государству.
По истечении установленного в 1537 г. срока перемирия, в Москве вновь начались переговоры с литовскими послами воеводой полоцким Яном Юрьевичем Глебовым, старостой мельницким Николаем Яновичем Тихоновским и писарем Николаем Николаевичем Ондрющевым. Новое русско-литовское соглашение было подписано 25 марта 1542 г., возобновив перемирие еще на 7 лет. Вновь продлили его 13 февраля 1549 г. На этот раз ставший обычным спор из-за пограничных территорий был осложнен нежеланием литовских послов воеводы витебского Станислава Петровича Кишки, маршалка Яна Юрьевича Комаевского и писаря Глеба Ясманова признать новый «царский» титул московского государя.
8. Борьба Московского государства с татарскими набегами в первой трети XVI в.