Гедимин устраивал своих сыновей на княжение в тех городах, жители которых еще являлись данниками Золотой Орды. Дань шла из Владимира, Луцка, Бреста, Пинска и Витебска, который подчинялся зависимому от татар Смоленску. Воцарение литовских князей в этих городах не вызвало военного конфликта с Золотой Ордой сразу только потому, что было найдено компромиссное решение: новые князья придерживались двойного вассалитета — от татарского хана и от литовского князя.

Дань с этих земель по-прежнему поступала в Золотую Орду, правда, в несколько уменьшенных размерах. Такую же дань выплачивал с Галицкой земли до 1357 года польский король, за что его упрекал в своих посланиях папа римский Иннокентий V. С Волынских земель дань в Золотую Орду поступала вплоть до конца XIV века — уже при внуках Гедимина.

Гедимин вынужден был пойти на этот компромисс, так как не мог позволить себе роскошь вести войну с гигантской Золотой Ордой в то время, как крестоносцы усиливали свой натиск с севера. Специальный налог — так называемая «ордынщина» — был возложен не только на волынские и поднепровские земли, но и на собственно литовские земли. В некоторых случаях «ордынщина» шла не в качестве дани татарам, а в великокняжескую казну на расходы, связанные с поддержанием мира с Золотой Ордой — посольские миссии, подарки и взятки ханам. Позднее литовские князья начали целиком оставлять этот налог себе, но его старинное название — «ордынщина» — осталось.

Войны Гедимина с Тевтонским орденом продолжались все эти годы с переменным успехом. Колоссальные жертвы, которые несли враждующие стороны, не давали преимущества никому из противников. В 1331 году литовцы совместно с войском Владислава Локетека разгромили крестоносцев в битве цод Пловцами в Польше.

В 1333 году произошел новый крестовый поход во главе с герцогом Баварским, во время которого была захвачена и сожжена важная литовская крепость Велона на реке Неман. По соседству с развалинами Велоны началось строительство мощного замка, который получил название Баербург.

В 1336 году ниже по течению Немана великий магистр тевтонцев Дитрих фон Альтенбург восстановил крепость Юргенбург. Таким образом, литовскопрусская граница неуклонно продвигалась на юг. От устья Немана ее уже отделяло свыше полутора сотен миль. С этого плацдарма крестоносцы получили превосходную возможность непосредственно угрожать не только Жемойтии, но и крупным городам Великого княжества Литовского.

Граница с государством крестоносцев пролегла в сорока милях от Каунаса, и в ста тридцати — от Вильнюса (Вильно). В 1337 году в Баербурге был основан католический костел, который должен был стать центром новой провинции после быстрого, по мнению руководства Тевтонского ордена, крещения Литвы.

Одновременно рыцари Ливонского ордена усилили свой напор с северо-востока. В 1334 году ливонский магистр Эберхард фон Мангейм дошел во главе своего войска до стен столицы Великого княжества Литовского и разграбил окрестности.

Гедимин предпринимал отчаянные попытки переломить ход событий в свою пользу. С этой целью он осадил в 1338 году Баербург. Однако осада завершилась тяжелым поражением литовцев. Магистр фон Альтенбург даже заявил, что под Баербургом был уничтожен весь цвет литовского рыцарства, поэтому, де, в дальнейшем крестоносцам не следует опасаться получить серьезный отпор в Литве.

Однако на этот раз великий магистр Тевтонского ордена выдал желаемое за действительное. Уже спустя три года литовцы перешли в новое наступление. В 1341 году им все же удалось захватить Баербург. При осаде этого замка князь Гедимин был смертельно ранен выстрелом из малой пушки — оружие, которое только начинали использовать крестоносцы.

В середине XIV века Прибалтика ускоренными темпами догоняла страны Западной Европы.