Так началось правление Гедимина. Одной из главных задач для него было создание мощной оборонительной линии, опираясь на которую можно было отбивать нападения крестоносцев. Очевидно, что у государства хватало материальных и людских ресурсов для реализации этой нелегкой задачи. Гедимин понимал, что положение требует напряжения всех сил. Он начинает строительство каменных замков по линии Троки, Вильно, Медники, Городно, Новогородок, Лида, Крево, Мядель. Со всех концов государства собирали строителей, княжеские тивуны сгоняли простой люд насыпать валы, копать рвы, тягать камни. Через столетия народ помнил об этих грандиозных стройках, и с тех пор еще живут выражения: «Каб цябе закаталі ў Вільню горы капаць!» или «Каб ты на Крэўскі замак каменне цягаў!».
Где-то в это время Гедимин переносит столицу Великого Княжества из Новогородка в Вильно и строит там, на Кривой горе, замок. Уже в 1323 году Вильно в Гедиминовых грамотах называется королевским городом. Считается, что именно Гедимин основал этот город. «Хроника Литовская и Жмойтская» повествует: «И в малых часех поехал после того князь великий Кгидимин в ловы от Трок за чотыри мили, и найдеть гору красную над рекою Вильнею, на которой знайдеть звера великого тура, и вбъеть его на той горе, где тепер зовуть Туря гора. И вельми было позно до Троков ехати, и станеть на луцэ на Швинторозе, где першых великих князей жыгали, и обночовал тут. И спечи ему там, сон видел, што ж на горе, которую зывали Крывая, а тепер Лысая, стоить волк железный великий, а в нем ревуть, як бы сто вильков. И очутился от сна своего и мовить ворожбиту своему именем Лиздейку, который был найден ув орлове гнезде, и был тот Лиздейко у князя Кгидимина ворожбитом найвышшым, а потом попом поганским: «Видел, дей, есми сон дивный». И споведал ему все, што ся ему у-во сне видело. И тот Лиздейко мовить господару: «Княже, волк великий жэлезный знаменуеть — город столечный тут будеть, а што в нем внутри ревуть, то слава его будеть слынути на весь свет». И князь великий Кгидымин назавтрее ж, не отеждчаючи, и послал по люди и заложыл город, один на Швинторозе Нижний, а другий на Крывой горе, которую тепер зовуть Лысою, и нарячеть имя тым городом Вильня».
Красочное предание. Но орденский посол Кондрад Кибург, побывавший в 1397 году в Вильно, писал в своем дневнике, что сон про волка увидел Лиздейко, который рассказал о нем великому князю. Верховный жрец был заинтересован в том, чтобы его резиденция Кривич-город стала столицей.
Историки В. Голубович и Е. Голубович на основе археологических раскопок установили, что Кривич-город находился на горе Кривой. По мнению историков, стародавнее городище Вильно под названием «Кривич-город» существовало уже в XI—XII веках, когда Полоцкому княжеству принадлежала часть литовских земель. Но, по данным археологии, поселение кривичей располагалось и на левом, восточном берегу реки Вилии. Возведенный Гедимином на Кривой горе замок защищал это поселение с запада. Поэтому орденский хронист Виганд Марбурский и назвал Вильно славянским городом. На перенос столицы повлияло и военное положение Вильно. Кибург писал: «В военном отношении положение города превосходно, в нем можно защищаться при незначительных укреплениях: многочисленные возвышения, ущелья и глубокие овраги доставляют весьма удобные случаи для нападения на осаждающих. При таком положении можно осаждающего впустить в город и, окружив, вырезать до последнего человека; был бы только гарнизон мужествен и верен и при том хорошо предводим — Вильне невозможно нанести особенного вреда. Из этого следует, что не сон о железном волке и не предсказание чернокнижника дали Гедимину мысль основать здесь столицу государства, но знание военного дела, причем не могли укрыться выгоды местоположения. Гедимин был великим полководцем своего времени и достоин нашего подражания, хотя он и язычник». Из всех этих фактов следует, что и до Гедимина в этой местности существовало городище, а он всего лишь построил там замок.
Гедимину еще приписывают завоевание в 1320 году Галицко-Волынского и Киевского княжеств. Об этом сообщается в белорусских летописях XVI века. Русский историк Н. Карамзин считал, что рассказ о походе в 1320 году Гедимина на Волынь и Киев — вымысел летописцев. Современные Гедимину исторические документы не упоминают об этом походе, и все же отрицать возможность похода Гедимина на Волынь и Киев нельзя. Вероятно, татарский набег в 1324 году на Литву был вызван этим походом. Но ни Киев, ни Волынь не были завоеваны Гедимином.