Параллельно с этим продолжалась война с Литвой, шедшая с 1534 по 1537 годы. В ходе боевых действий русские войска в очередной раз разорили территорию Великого княжества Литовского и построили на его землях крепость Себеж. Литовские же войска под командованием Юрия Радзивилла и Александра Вишневецкого штурмом взяли Гомель и безуспешно осаждали Киев. В дальнейшем они провели серию набегов на юг русского государства, не делая разницы между московскими и сестрорецкими владениями. Языческим силам Чернигова, Новгорода-Северского, Стародуба, Брянска и Рославля волей-неволей пришлось взаимодействовать с московскими воеводами Киева, Любеча и Смоленска. В конце концов Москва и Литва все-таки подписали перемирие на условиях сохранения текущей ситуации (фактически в результате войны произошел размен Гомеля на Себеж).
Еще одной "горячей точкой" Великого княжества Московского стала восточная граница. Из-за отвлеченности основных московских сил на западные границы и бездеятельности Сестрорецкого князя в Казанском ханстве произошел государственный переворот и к власти вновь пришел Сафа-Гирей. Он начал проводить более осторожную политику чем ранее (и чем Сигизмунд Литовский) и начал боевые действия только против Москвы (его войска имели прямой приказ не нападать на языческие земли, и несколько нарушителей были даже казнены). Следствием этого стали крайне успешные набеги 1536–1545 годов, защиты от которых русские так и не нашли. Особенно разрушительными стали походы зимы-весны 1536 года, когда восток Московского княжества буквально обезлюдел. Хан Сафа-Гирей избрал на этот раз новую тактику. Он не стал организовывать похода всеми силами на Москву, и не стал осаждать русские города. Вместо этого сравнительно небольшие мобильные отряды татарской конницы производили нападения на все ключевые пункты Российского государства вдоль его восточных границ. Одновременному нападению подверглось практически всё российско-казанское пограничье. Организовать защиту московские власти не сумели.
Как вариант — просто не успели, т. к. летом 1536 года армия была собрана и татарские отряды отступили, а в последующем стали действовать более осторожно.
Тем не менее набеги повторяются ежегодно и поражения казанцев выглядят редкими эпизодами. Так в 1539 году их разбивают Муромские войска Шах-Али, а в 1540 году набег срывается из-за страха перед муромскими татарами. В этот период защиту Московского княжества от татар обеспечивают исключительно Муромские отряды.
В 1537 году в Москве произошел государственный переворот. Княжеская партия взяла реванш, к власти пришли братья Василий и Иван Шуйские. Предположительно Елена Глинская была отравлена. Князь Овчина Оболенский казнен (через семь дней после смерти Елены). Его родственники и сторонники были отправлены в ссылку. Наиболее видные представители Боярской Думы отстраняются от дел. Митрополит Даниил, сыгравший важную роль в отстранении Думы от власти, также оттесняется на второй план. Его попытка изменить ситуацию и привести к власти князя Ивана Бельского оканчивается провалом. Бельский арестовывается.