«Не встречая нигде войск противника, которых, как мы знаем, было всегда весьма трудно собрать вовремя литовским великим князьям, наша рать, разорив неприятельские области, подошла, невзирая на страшные снега и жестокие морозы, почти к самой Вильне, где сидел встревоженный Сигизмунд, и затем, не предполагая осаждать этот сильно укрепленный город, она торжественно вернулась назад. В то же время воеводы, князья Федор Телепнев и Тростенские ходили с таким же успехом от Стародуба к Мозырю, Турову и Могилеву, — тоже нигде не встречая неприятельских войск и всюду внося ужас и опустошение».
На следующий год (1535) власти ВКЛ в дополнение к своему шляхетскому ополчению наняли 5 тысяч польских жолнеров, а король дал им одну тысячу конников и 500 пехотинцев из своего войска. Поляки соединились с литвинами в конце мая под Речицей.
Первоначально это войско должно было идти к Смоленску. Но в Москву явились перебежчики, слуги князей Семена Вельского и Ляцкого, предупредившие московские власти о направлении главного удара и его сроках. Навстречу литовцам из Москвы в мае вышли крупные силы: большой полк князя Василия Васильевича Шуйского, передовой полк князя Ивана Овчины-Телепнева-Оболенского. Они наносили удар в направлении Кричев — Могилев, сжигая все селения на своем пути.
С северного направления в Литву должны были вторгнуться отряды новгородцев и псковитян под предводительством князей Бориса Горбатого и Михаила Воронцова. Им предписывалось быстро построить крепость на берегу Себежского озера, сделать ее своим опорным пунктом, а затем идти на соединение с Шуйским и Телепневым-Оболенским. Но эти воеводы только отчасти исполнили указание: послали воеводу Бутурлина строить Себежскую крепость, сами же разместились в Опочке и дальше не шли вплоть до осени.
Войсками Литвы командовали великий гетман Литвы Юрий Радзивилл, великий гетман Короны Ян Тарновский, киевский воевода Андрей Немирович (Немира), князь Илья Острожский, а также московский беглец, князь Семен Вельский. Избегая решительного сражения с высланной против них ратью, они двинулись в сторону Северской земли, на 200 верст южнее направления главного удара московитов. В июне 1535 года их войска осадили Гомель и начали артиллерийский обстрел гомельского замка:
«А так в середу весь день на замок стрелба била, а потом с середы на четверг всю ночь и в четверг мало не весь день с наших дел (орудий) стрелбу чинили»…
Наместник Гомеля, князь Дмитрий Щепин-Оболенский оказался трусом. С гарнизоном и частью артиллерии он ушел в Москву, где его немедленно бросили в темницу за «измену»:
«Не храбр и страшлив, видев люди многие и убоявся, из града побежал, дети боярские з ним же и пищалники»… «Тутошние люди немногие, видя воеводское нехрабрство и страхование, здаша град» (16 июля).
В отличие от Гомеля, город Стародуб, где воеводой был князь Федор Телепнев-Овчина-Оболенский (родной брат Ивана), сопротивлялся отчаянно. Тогда немецкие инженеры прорыли подкоп под стены города и одновременно взорвали сразу несколько фугасов. В образовавшийся пролом ворвались литовские воины: