В мае 1471 года Иван III послал в Новгород «разметные грамоты» — формальное извещение о начале войны.
13 июля на берегу реки Шелони новгородцы были разбиты наголову. Иван III двинулся с главным войском к Новгороду. Между тем из Литвы не было никакой помощи. Народ в Новгороде заволновался и отправил своего архиепископа Феофила просить у великого князя пощады.
Кажется, достаточно было одного усилия, чтобы разгромить Новгород и окончить войну небывалым триумфом. Однако Иван III устоял перед искушением. 11 августа 1471 года близ Коростыни он заключил договор, подводивший итог всей московско-новгородской войне. Как бы снисходя усиленному заступничеству за виновных митрополита, своих братьев и бояр, великий князь объявил новгородцам свое милосердие: «Отдаю нелюбие свое, унимаю меч и грозу в земле новгородской и отпускаю полон без окупа».
Условия, выдвинутые победителями, оказались неожиданно мягкими: новгородцы присягали на верность Ивану III и обязывались в течение года выплачивать ему контрибуцию. Внутреннее устройство Новгорода оставалось прежним. Волоколамск и Вологда окончательно переходили к Москве.
И, самое главное, по Коростынскому договору Новгород признавал себя «отчиной» великого князя Московского, а самого Ивана III — высшей судебной инстанцией для горожан.
Вскоре Иван решил и личные проблемы. Внезапная кончина первой жены Ивана III, княгини Марии Борисовны, 22 апреля 1467 года заставила 27-летнего великого князя московского думать о новой женитьбе.
Присоединение Москвы к общеевропейскому союзу для борьбы с Турцией стало мечтой западной дипломатии. Внедрение Турции на побережье Средиземного моря в первую очередь угрожало Италии. Поэтому уже с 70-х годов XV века как Венецианская республика, так и папский престол с надеждой взирали на далекий Северо-Восток. Этим объясняется то сочувствие, с которым был встречен и в Риме, и в Венеции проект брака могущественного русского государя с находившейся под покровительством папы наследницей византийского престола Софией (Зоей) Фоминичной Палеолог. Через посредство греческих и итальянских дельцов проект этот был осуществлен 12 ноября 1472 года. Посылка в Москву одновременно с невестой и полномочного «легата» (посла) папы Сикста IV — Бонумбре, снабженного самыми широкими полномочиями, свидетельствовала о том, что папская дипломатия связывала с этим брачным союзом большие планы. Венецианский совет со своей стороны внушал Ивану III мысль о его правах на наследие византийских императоров, захваченное «общим врагом всех христиан», то есть султаном, потому что «наследственные права» на Восточную империю, естественно, переходили к московскому князю в силу его брака.
Однако все эти дипломатические шаги не дали никакого результата. У Русского государства были свои неотложные международные задачи. Их Иван III неуклонно проводил в жизнь, не давая себя прельстить никакими Ухищрениями Рима или Венеции.
Брак московского государя с греческой царевной был важным событием русской истории. Он открыл путь связям Московской Руси с Западом. С другой стороны, вместе с Софьей при московском дворе утвердились некоторые порядки и обычаи византийского двора. Церемониал стал величественнее и торжественнее. Сам великий князь возвысился в глазах современников. Они заметили, что Иван после брака на племяннице императора византийского явился самовластным государем на московском великокняжеском столе; он первый получил прозвание Грозного, потому что был для Князей дружины монархом, требовавшим беспрекословного повиновения и г строго каравшим за ослушание.
Именно в то время Иван III стал внушать страх одним своим видом. Женщины, говорят современники, падали в обморок от его гневного взгляда. Придворные, со страхом за свою жизнь, должны были в часы досуга забавлять его, а когда он, сидя в креслах, предавался дремоте, они неподвижно стояли вокруг, не смея кашлянуть или сделать неосторожное движение, чтобы не разбудить его. Современники и ближайшие потомки приписали эту перемену внушениям Софии. Герберштейн, бывший в Москве в княжение сына Софии, говорил о ней: «Это была женщина необыкновенно хитрая, по ее внушению великий князь сделал многое».
Уже одно то, что невеста согласилась поехать из Рима в далекую и ведомую Москву, свидетельствует о том, что это была смелая, энергичная и склонная к авантюрам женщина. В Москве ее ожидали не только почести, оказываемые великой княгине, но также враждебность местного духовенства и наследника престола. На каждом шагу ей приходилось отстаиват свои права. Вероятно, она многое делала для того, чтобы найти поддержку и сочувствие в московском обществе. Но лучшим способом утвердить себя было, конечно, деторождение. И как монарх, и как отец великий князь хотел иметь сыновей. Желала этого и сама Софья. Однако, на радость доброжелателям, частые роды принесли Ивану подряд трех дочерей — Елену (1474), Феодосию (1475) и опять Елену (1476). Встревоженная Софья молила Бога и всех святых о даровании сына.