В первые годы правления Ольгерду и Кейстуту пришлось перейсить немало неудач. В 1345—1348 гг. они с трудом отражали непрерывные нападения орденских рыцар|ей. 2/февраля 1348 г. в битве над рекой Стравой войско, собранное братьями с литовских и славянских земель Великого княжества, потерпело тяжелое поражение и было вынуждено отступить. В этой битве погиб и Наримунт Гедиминович. Резко ослабло влияние Гедиминовичей в Новгороде и Пскове. В 1349 г. польские
войска заняли Галицкую землю, Брест, Подляшье. В 1350 г. Ольгерд вынужден был заключить мир с московским князем Симеоном Гордым, отказавшись от установленного незадолго до этого сюзеренитета над Смоленской землей, а его брат Дмитрий-Любарт женился на племяннице московского князя (дочери Константина Ростовского). В этой трудной ситуации Ольгерд проявил незаурядные дипломатические способности и сумел не только восстановить позиции Литвы на Руси, но и найти возможность гораздо более активно участвовать в политической борьбе между претендентами на Владимирское великое княжение. Его союзником стало Тверское княжество. Брак с княжной Ульяной Александровной Тверской (на сестре которой, кстати, был женат Симеон Гордый) придал соглашению противников Москвы традиционный для феодализма «семейный» оттенок. Мирно закончился и спор с Польшей за Галицкую Русь; в 1352 г. Великое княжество Литовское отказалось от претензий на эту территорию. Обеспечив безопасность юго-восточных и восточных окраин государства, Ольгерд и Кейстут выдвинули в 1358 г. программу объединения под властью Великого княжества Литовского и Русского всех балтских и восточнославянских земель, программу, направленную прежде всего против Ордена и Золотой Орды. В ответ на предложение польского короля Казимира IV, папы Климента VI и императора Карла IV принять католичество Ольгерд выдвинул условие ликвидации орденских владений в Прибалтике — он остроумно предложил, чтобы Орден «поместился в пустянях между татарами и русскими для защиты их от нападения татар и чтобы Орден не сохранял никаких прав у русских, но вся Русь принадлежала литовцам»; он требовал возвращения Литве захваченных рыцарями земель ятвягов, пруссов, латышей, понимая, разумеется, что Орден никогда не согласится добровольно уйти с насиженных мест.
В те годы Золотая Орда раздиралась кровавыми междоусобицами. Обострилась борьба и между княжествами Владимирской Руси. После смерти энергичного Симеона Гордого его брат Иван Красный не сумел сохранить завоеванное Москвой лидерство, хотя и получил ярлык на великое княжение. После его смерти ярлык перешел к суздальскому князю Дмитрию Константиновичу; была нарушена традиция, подвергнуто сомнению наследственное право потомков Калиты на лидерство — причиной было малолетство московского князя Дмитрия. В результате создалась ситуация, когда фактически ни один из князей Северо-Восточной Руси не мог контролировать действия соседей. В течение ряда лет московской дипломатии предстояло сосредоточить свои усилия на решении чисто региональной задачи — восстановлении своего лидерства в пределах Северо-Восточной Руси. И вновь Вильно оказался единственным центром, способным отстаивать общерусскую программу, в тот период имевшую четко выраженную антиордынскую, освободительную направленность. Ольгерд возобновляет нажим на Смоленскую и Брянскую земли. В 1356 г. он захватывает Ржеву, в 1359 г.— принадлежавший Смоленскому княжеству Мстиславль и, вероятно, Белую, в 1362 г.— Торопец. Как считает ряд исследователей, именно в 50-е годы XIV в. к Великому княжеству Литовскому перешли и земли по Березине, среднему Поднепровью, Сожу (с Пропойском, Чечерском, Речицей и Любечем). Таким образом, его владения вплотную подступали к Чернигово-Северской земле, где все еще правили многочисленные потомки местной ветви Рюриковичей, а также Киевщине, со времен Гедимина находившейся в орбите литовского влияния, но, как и Черниговская земля, сохранявшей зависимость от Орды. Ольгерд возвращается к старой идее подчинения своему влиянию православной иерархии, поддержке которой московские князья во многом обязаны были своими успехами. Не имея возможности устранить с митрополичьей кафедры промосковски настроенного Алексия, Ольгерд (как в свое время Гедимин) предпринимает попытки добиться особой, литовской митрополии в Киеве. Быть может, он рассчитывал, что древняя киевская кафедра позволит ему в будущем претендовать на церковную власть над всей русской землей. Еще в 1352 г., при жизни враждебного ему Феогноста, Ольгерд обратился в Константинополь с просьбой возвести в сан митрополита своего кандидата — Феодорита. После отказа греков он добился посвящения от болгарского патриарха, утвердил Феодорита в Киеве и помог ему распространить свою юрисдикцию на все славянские земли Великого княжества Литовского. Константинополь, разумеется, Феодорита не признал. Однако, не желая терять контроля над большей частью русской митрополии, хитроумные греки предложили компромисс, в то время, вероятно, в принципе устроивший Ольгерда. Московский кандидат — Алексий — был назначен на общерусскую (киевскую) митрополию, а предложенныйОльгердом тверич Роман — на вновь созданную митрополию в Новогрудок, причем ему были подчинены также Полоцкая, Туровская епархии, а затем и Галицко-Волынская земля. Тем самым возникли условия для нейтрализации церковно-политического влияния Москвы в этом регионе, что, разумеется, усиливало позиции Ольгерда. Но антилитовская политика возглавляемой Алексием церковной иерархии Северо-Восточной Руси, по-видимому, оставалась одним из решающих препятствий для расширения влияния Ольгерда в этом регионе. Довольно прочные позиции сохранял Алексий и в Киеве; Роману удалось утвердиться там лишь на короткий срок.