Об отношениях Москвы с татарами между 1365 и 1368 гг. нам ничего не известно. Однако в 1368 г. давно назревавший между московским и тверским князьями конфликт вылился в открытое противостояние, в котором на стороне Твери выступили сначала Литва, а потом и Орда. Как мы уже говорили ранее, около 1360 г. Ольгерд, воспользовавшись ослаблением Москвы, сумел подчинить своей власти Смоленск и Брянск. Дальнейшее продвижение литовцев на юг и восток неизбежно должно было привести их в соприкосновение с татарами. В 1362 г. Ольгерд посадил в Киеве своего сына Владимира вместо брата Гедимина князя Фёдора, правившего там ещё с 1324 г.: «Олгеръдъ… Киевъ под Федором князем взят и посади въ немъ Володымера, сына своего»186. Тогда же Ольгерду удалось подчинить себе Чернигово-Северские земли, о чём можно заключить по краткому упоминанию русских летописей о захвате литовцами Коршева – города на крайнем юго-востоке Чернигово-Северщины: «Того же лета Литва взяли Коршевъ и сотворишас [я] мятежи и тягота людемъ по всеи земли»187. Осенью того же года Ольгерд на Синих Водах разбил войска трёх татарских правителей и подчинил своей власти Подолье: «Олгердъ победи трехъ царковъ татарскихъ и з ордами ихъ, си есть Котлубаха, Качзея, Дмитра; и оттоле от Подоля изъгна власть татарскую»188. Западные улусы Орды, включая Киевщину, Чернигово-Северщину и Подолье, в это время входили в сферу влияния Мамая, однако ни о каких конфликтах между литовцами и татарами Мамаевой орды источники не упоминают. Объяснить это можно лишь заключением договора между Ольгердом и Мамаем о разделе сфер влияния в юго-западной Руси.
Свидетельства о подобном договоре имеются в более поздних документах Великого княжества Литовского, касающихся его отношений с татарами. Так, согласно наказу от 27 ноября 1500 г. великого князя Александра Казимировича Дмитрию Путятичу, направленному послом к крымскому хану Менгли-Гирею, посол должен был заявить хану, в частности, что «предкове твои, первыи цари, зъ давныхъ часовъ были съ предки господаря нашого, зъ великими князи Литовскими, почонъ отъ великого царя Тактамыша и отъ великого князя Олкгирда, въ братстве и въ прыязни и въ правде твердой»189. В послании тому же Менгли-Гирею великого князя Сигизмунда Старого от 26 октября 1507 г. хан призывался «во всим братство, приятельство верное с нами заховати по тому, как и предкове наши, почон от царя Токтамыша и от великого князя Олкгирда аж до отцов наших Казимира, короля, и Ачжи Кгирея, царя»190. Наконец, в своем послании к Менгли-Гирею от 14 ноября 1512 г. Сигизмунд Старый упоминал «давние дела, как предьки наши с твоими предки, почонши от великого князя Олкгиръда, и от Витовта, а з вашое стороны от Тактомыша царя, аж до отцов наших, Казимира короля и Ачжикгирия царя, в котором братстве и приязни они промежку собе были»