Составленное в Московской Руси «Сказание о князьях Владимирских» называет Гедимина бывшим конюхом князя Витенеса. Витенес якобы был убит громом, а женившийся на его вдове Гедимин захватил власть над Литвой и Западной Русью, незаконно присвоив дань, которую он собирал с этих земель для московского князя. Эта колоритная легенда отразилась и в литовских хрониках XVI в., приписывающих Гедимину убийство Витенеса. Большинство историков, впрочем, считает ее позднейшей выдумкой (с целью дискредитировать литовскую династию, представив Гедиминовичей узурпаторами власти). Некоторые летописи называют Гедимина сыном Витенеса, но, вероятнее всего, они были братьями.
Гедимин царствовал четверть века, раздвинув далеко на юг и восток границы своей державы. В те годы московские и тверские князья, оспаривая в Орде Владимирское великое княжение, еще не помышляли о решительной схватке с ней. Именно Великое княжество Литовское и Русское стало при Гедимине центром антиордынской борьбы; опираясь на его поддержку, западнорусские земли надеялись сбросить ненавистное иго. В 30-е годы XIV в. заключил с Гедимином договор о взаимной помощи смоленский князь Иван Александрович, признавший себя «младшим братом», т. е. вассалом, литовского государя. Разгневанный этим союзом хан Узбек в 1339 г. послал на Смоленск свою рать с Тавлубием-мурзой. Участвовал в этом походе и московский князь Иван Калита. Встретив мужественное сопротивление смолян, поддержанных литовцами, их враги «стояша ратию оугороде не много дни, а города не взяша». После этого Орда должна была смириться с отказом Смоленска платить дань. Как пишет местный историк Д. И. Маковский, «с этого момента... Смоленск не знал татарского ига». С потерей ханом власти над Смоленщиной был положен окончательный предел распространению власти Золотой Орды на западных русских землях.
Гедимин сохранил контроль над древним Полоцком, где уже давно утвердилась литовская династия. После смерти сына Товтивила, Константина Безрукого, полоцкий «стол» достался не его сыну, а брату Гедимина Воину. Около 1318 г. старший сын Гедимина Ольгерд женился на дочери витебского князя и вскоре унаследовал удел умершего тестя. Подчинилось Гедимину и Минское княжество. На западе войска литовского князя довольно успешно отражали нападения крестоносцев. Как и Миндовг, Гедимин умело балансировал между восточным и западным христианством. Не ущемляя прав православной церкви, он пытался влиять на церковные дела, чтобы поставить в митрополиты своего кандидата, а в случае неудачи — оторвать подвластные ему земли от общерусской митрополии, создав для Великого княжества Литовского особую церковную иерархию. Одновременно он не прекращал контактов с католической церковью. Заключив соглашение с Ригой, Гедимин с ее помощью отправил несколько посланий папе Иоанну XXII, обещая ему крестить Литву по западному обряду и обвиняя орденских рыцарей в том, что они жестокими набегами отвращают литовцев от христианства. В 1324 г. в Литву прибыло папское посольство. Но против планов введения католицизма выступила и языческая литовская знать, и «русины», т. е. представители православного населения, с позицией которого Гедимин не мог не считаться. «Король Литвы и Руси», как именуют Гедимина некоторые западные документы того времени, прекрасно понимал, что источником силы его государства являются обширные славянские земли.