Неэффективность вассальной зависимости как политического института особенно наглядно проявилась в отношениях с Казанским ханством. В XV в. собирать ежегодную дань с вассальных земель, признаваемых равными по уровню политического развития, было уже не принято, потому что нереально (как показал опыт ВКМ и Большой Орды). Для обеспечения поступления дани необходимо было держать на месте такой аппарат принуждения, что ни о какой самостоятельности «вассала» речи идти не могло. Решающим фактором сохранения вассальных отношений становилась не решительность сюзерена, а готовность вассала поддерживать эти отношения. За неполные 70 лет (между 1484 и 1552 гг.) Москва восемь раз добивалась утверждения казанским ханом собственного кандидата, обычно выходца из Касимовского ханства. Одна за другой при Иване III и его сыне и наследнике Василии III (1479−1533) отправлялись военные экспедиции на Казань для возведения на престол лояльного Москве правителя, подавления вспыхнувшего против него мятежа или отражения набега казанцев. Хотя многие экспедиции заканчивались безрезультатно или разгромом московских войск, и в общей сложности открыто враждебные правители (ориентировавшиеся на Крымское ханство) занимали казанский престол почти столь же продолжительное время, что и признававшие зависимость от Москвы, политика в отношении Казани не менялась многие десятилетия. Ставка делалась на личную лояльность очередного казанского хана, мысль о прямом подчинении ханства ВКМ, кажется, даже не приходила в голову московским властям.
Установка на решение «казанской проблемы» традиционным назначением верного вассала не сразу изменилась даже после того, как к власти в Казани в 1521 г. в результате переворота пришел Сахиб Гирей (Сахиб Герай), младший брат крымского хана Мехмед Гирея (Герая), переориентировавший Казань на Крым. Тем же летом он вместе с огромной армией брата вторгся в пределы ВКМ, захватив и разорив Нижний Новгород и Владимир. Объединенные крымско-казанско-литовские силы осадили Москву, разграбили округу и отступили, лишь вытребовав у Василия III официальную грамоту с признанием его данником и вассалом крымского хана! (Эту грамоту хитростью отобрал у возвращавшихся с добычей крымцев воевода Переяславля-Рязанского Хабар Симский: Мехмед Гирей потребовал сдачи гарнизона на основании признания себя сюзереном Василия III; дотошный воевода потребовал предъявить подтверждающий документ, а когда послы хана принесли грамоту, забрал ее и приказал артиллерии рассеять неприятеля.)
В 1523 г. казанский хан приказал казнить московских послов и купцов, арестованных двумя годами ранее, во время захвата власти, и Василий III организовал новый военный поход. В отличие от многих прошлых карательных экспедиций, помимо разорения земель ханства и военных столкновений, в этот раз русские войска применили новую тактику: в сентябре 1523 г. был построен город Васильев Новгород (Васильев, Васильсурск) при впадении реки Суры в Волгу, примерно на половине пути от Нижнего Новгорода до Казани. Крепость была возведена у подножия горы, на которой находился разгромленный русскими город Цепель — столица горных мари, а неподалеку — священная роща марийцев, посвященная верховному богу Кого Йымы (луговомарийск. — Кугу Юмо). Впервые был создан форпост ВКМ на территории Казанского ханства и установлен контроль над частью территории и подданного населения Казанского ханства. Примечательно, что это решение вызвало широкую критику в Москве: высказывалось опасение, что теперь будет трудно установить дружественные отношения с Казанью, которые по-прежнему рассматривались как стратегическая цель. Да и сам Василий III снарядил поход 1523 г. по двум причинам: во-первых, из-за убийства московских послов и купцов, во-вторых, поскольку Сахиб Гирей «стал царем без ведома великого князя». То есть сам факт игнорирования воли бывшего сюзерена воспринимался столь же значимой причиной для войны, как и конкретные враждебные действия. Задача аннексии Казанского ханства — подобно тому, что происходило параллельно на западе, где одна за другой присоединялись к ВКМ земли ВКЛ, — не ставилась. В следующем, 1524 г., на Казань были отправлены еще более крупные силы, которые осадили город, но не могли его взять. Во главе похода стоял бывший хан Казани Шах-Али, свергнутый Сахиб Гиреем в 1521 г.; очевидно, в случае успеха осады он должен был вернуть себе казанский трон в качестве лояльного вассала Москвы.