Успешное противостояние Большой Орде и Литве становилось возможным для Ивана III лишь при условии союза с Крымом. На это и были направлены усилия московской дипломатии. Иван привлек на свою сторону нескольких влиятельных крымских «князей». Они побудили к сближению с Москвой и самого хана Менгли-Гирея.
Иван III домогался этого союза ценой больших уступок. Он соглашался даже, если потребует хан, титуловать его «государем» и не щадил расходов на «поминки», то есть ежегодные подарки для своего татарского союзника. Русской дипломатии удалось в конечном итоге добиться заключения желанного союза. Крымские татары периодически стали совершать набеги на литовские владения, проникая далеко в глубь страны, до Киева и дальше. Этим они не только наносили материальный ущерб великому княжеству Литовскому, но и ослабляли его обороноспособность. Союз с Менгли-Гиреем был связан и с другой проблемой русской внешней политики конца XV — начала XVI века — проблемой окончательной ликвидации зависимости от Золотой Орды. При ее разрешении Иван III более чем когда-либо действовал не столько оружием, сколько дипломатическим путем.
Союз с Крымом и был решающим моментом в борьбе с Золотой Ордой. К союзу были привлечены ногайские и сибирские татары. Хан Ахмат при отступлении от Уфы был убит в 1481 году татарами сибирского хана Ибаха, а в 1502 году Золотая Орда была окончательно разгромлена Менгли-Гиреем.
Первая московско-литовская война началась в 1487 году и продолжалась до 1494 года. Предметом спора в этой войне были пограничные области с неопределенным или двойственным политическим статусом. На южной и западной границе под власть Москвы то и дело переходили мелкие православные князья со своими вотчинами. Первыми передались князья Одоевские, затем Воротынские и Белевские. Эти мелкие князья постоянно ссорились со своими литовскими соседями — фактически на южных границах не прекращалась война, но и в Москве и в Вильно долгое время сохраняли видимость мира.
Те, кто переходили на московскую службу, немедленно получали уже в качестве пожалования свои прежние владения. Для защиты «правды» и восстановления «законных прав» своих новых подданных Иван III отправлял небольшие отряды.
Замысел кампании 1487–1494 годов состоял в том, чтобы достичь успеха незаметно, без лишнего шума. Иван III избегал широкомасштабной войны с Литвой. Это могло вызвать аналогичные действия со стороны Литвы, Польши, в то же время сплотить «верховных князей» и толкнуть их в Объятия Каземира.
В июне 1492 года король польский и великий князь литовский Казимир IV скончался. Его сыновья разделили наследство. Ян Ольбрахт получил польскую корону, а Александр Казимирович — литовский престол. Это значительно ослабило потенциал противника Москвы.
Иван III вместе с Менгли-Гиреем немедленно начал против Литвы войну. Хотя, по заявлению московских дипломатов, войны не было; происходило только возвращение под старую власть московского великого князя тех его служебных князей, которые либо временно отпали от него в смутные годы при Василии Васильевиче, либо и прежде служили «на обе стороны».
Дела пошли удачно для Москвы. Воеводы взяли Мещовск, Серпейск, Вязьму. Князья Вяземские, Мезецкие, Новосильекие и другие литовские владельцы переходили на службу к московскому государю. Александр Казимирович сообразил, что трудно будет ему бороться с Москвой и Менгли-Гиреем; он задумал жениться на дочери Ивана, Елене, и таким образом устроить прочный мир между двумя государствами. Переговоры шли вяло до января 1494 года. Наконец 5 февраля был заключен мир, по которому Александр признавал новые московские границы, новый титул московского великого князя. При таких условиях Иван согласился выдать за него свою дочь.
Мирный договор с Литвой можно считать важнейшим военным и дипломатическим успехом Ивана III. «Значение мирного договора для России было велико, — отмечает известный историк А.А. Зимин. — Граница с Литовским княжеством на западе значительно отодвигалась. Создавалось два плацдарма для дальнейшей борьбы за русские земли: один был нацелен на Смоленск, а другой вклинивался в толщу северских земель».
Как и следовало ожидать, этот «брак по расчету» оказался тяжелым и для Александра, и для Елены.
В 1500 году отношения между Москвой и Вильно перешли в явную вражду по поводу новых переходов на сторону Москвы князей, подручных Литве. Иван послал зятю «разметную грамоту» и вслед за тем отправил на Литву войско. Крымцы, по обычаю, помогали русской рати. Многие украинские князья, чтобы избежать разорения, поспешили передаться под власть Москвы. В 1503 году было заключено перемирие сроком на шесть лет. Вопрос о принадлежности захваченных Иваном земель, площадь которых составляла около трети всей территории Великого княжества Литовского, оставался открытым. Литва продолжала считать их своими. Однако фактически они оставались в составе Московского государства.