Первым делом Олега в Украйне было построение городов, острожков, сколько для утверждения своей власти в новых областях, столько же и для защиты со стороны степей. Потом нужно было определить отношения к старым областям, к племенам, жившим на северном конце водного пути, что было необходимо вследствие нового поселения на юге; главная форма, в которой выражались отношения этих племен к князю, была дань, и вот Олег уставил дани славянам (ильменским), кривичам и мери; новгородцы были особо обязаны платить ежегодно 300 гривен для содержания наемной дружины из варягов, которые должны были защищать северные владения. Сперва, как видно, эта стража состояла исключительно из варягов, потом, когда эта исключительность исчезла, то вместо варягов встречаем уже общее название гридей, наемная плата увеличивалась по обстоятельствам: так, после раздавалась гридям уже тысяча гривен вместо трехсот; прекратилась эта выдача денег со смертию Ярослава I, вероятно, потому, что с этого времени новгородцы не могли более опасаться нападений ни с которой стороны, а, может быть, также между ними и князьями сделаны были другого рода распоряжения относительно внешней защиты.
Построив города и установив дани у племен северных, Олег, по преданию, начинает подчинять себе другие племена славянские, жившие к востоку и западу от Днепра. Прежде всего Олег идет на древлян, у которых давно шла вражда с полянами; древляне не поддались добровольно русскому князю, их нужно было примучить, чтобы заставить платить дань, которая состояла в черной кунице с жилья. В следующем, по счету летописца, году (884) Олег пошел на северян, победил их и наложил дань легкую; эта легкость должна объясняться малым сопротивлением северян, которые платили дань козарам и, следовательно, могли легко согласиться платить ее русскому князю; с своей стороны Олег должен был наложить на них только легкую дань, чтобы показать им выгоду русской зависимости перед козарской; он, по преданию, говорил северянам: "Я враг козарам, а вовсе не вам". Радимичи, платившие также дань козарам, в следующем году не оказали никакого сопротивления Олегу, он послал спросить у них: "Кому даете дань?" Те отвечали: "Козарам". "Не давайте козарам, - велел сказать им Олег, - а давайте лучше мне", и радимичи стали платить русскому князю те же два шляга от рала, которые давали козарам. Но не так легко было справиться с теми племенами, которые прежде были независимы, не платили никому дани, не хотели и теперь платить ее Руси; мы видели сопротивление древлян; потом, слишком в двадцать лет, по счету летописца, Олегу удалось покорить дулебов, хорватов и тиверцев, но угличей не удалось. Только в 907 году Олег собрался в поход на греков; оставив Игоря в Киеве, он пошел со множеством варягов, славян (новгородцев), чуди, кривичей, мери, полян, северян, древлян, радимичей, хорватов, дулебов и тиверцев, пошел на конях и в кораблях; кораблей было 2000, на каждом корабле по 40 человек. Разумеется, историк не имеет обязанности принимать буквально этот счет, для него важен только тон предания, с каким оно хранилось в народе и из которого видно, что предприятие было совершено соединенными силами всех племен, подвластных Руси, северных и южных, а не было набегом варяжской шайки: отсюда объясняется робость греков, удача предприятия. Когда русские корабли явились пред Константинополем, говорит предание, то греки замкнули гавань, заперли город. Олег вышел беспрепятственно на берег, корабли были выволочены, ратные рассеялись по окрестностям Царя-града и начали опустошать их: много побили греков, много палат разбили и церквей пожгли; пленных секли мечами, других мучили, расстреливали, бросали в море. Предание прибавляет, что Олег велел поставить лодки свои на колеса, и флот при попутном ветре двинулся на парусах по суше к Константинополю. Говоря просто, Олег приготовился к осаде города; греки испугались и послали сказать ему: "Не губи город, мы беремся давать тебе дань, какую хочешь". Олег остановился; то же предание рассказывает, что греки выслали ему кушанье и напитки с отравою, что Олег догадался о коварстве и не коснулся присланного и что тогда греки в испуге говорили: "Это не Олег, но святый Димитрий, посланный на нас богом". Приведенный рассказ замечателен по тому представлению, которое имели о характере греков и о характере вещего Олега: самый хитрый из народов не успел обмануть мудрого князя! Олег, продолжает летопись, отправил к императору послов - Карла, Фарлофа, Велмуда, Рулава и Стемира, которые вытребовали по 12 гривен на корабль да еще уклады на русские города: Киев, Чернигов, Переяславль, Полоцк, Ростов, Любеч и другие, потому что в тех городах сидели Олеговы мужи; Олег требовал также, чтобы русь, приходящая в Царьград, могла брать съестных припасов, сколько хочет; гости (купцы) имеют право брать съестные припасы в продолжение шести месяцев - хлеб, вино, мясо, рыбу, овощи; могут мыться в банях, сколько хотят, а когда пойдут русские домой, то берут у царя греческого на дорогу съестное, якори, канаты, паруса и все нужное. Император и вельможи его приняли условия, только с следующими изменениями: русские, пришедшие не для торговли, не берут месячины; князь должен запретить своим русским грабить села в стране греческой; русские, пришедши в Константинополь, могут жить только у св. Мамы, император пошлет переписать их имена, и тогда они будут брать свои месячины - сперва киевляне, потом черниговцы, переяславцы и другие; входить в город будут они одними воротами, вместе с чиновником императорским, без оружия, не более 50 человек и пусть торгуют, как им надобно, не платя никаких пошлин. Из этих условий видна недоверчивость греков к русским, которые любили при удобном случае переменить характер купцов на характер воинов. Императоры Леон и Александр целовали крест в соблюдении договора; привели также к присяге Олега и мужей его, те клялись по русскому закону: оружием, Перуном, богом своим, Волосом, скотьим богом, и таким образом утвердили мир. Предание прибавляет, будто Олег велел руси сшить паруса шелковые, а славянам - полотняные, будто воины повесили щиты свои на воротах цареградских в знак победы, и когда пошли они домой, то русь подняла паруса шелковые, а славяне - полотняные, но ветер разодрал их; тогда славяне сказали: примемся за свои холстинные паруса, не дано славянам парусов полотняных. Это предание любопытно потому, что в нем видно различие между русью и славянами, различие в пользу первой. Под именем руси здесь должно принимать не варягов вообще, но дружину княжескую, под славянами - остальных ратных людей из разных племен; естественно, что корабль княжеский и другие, везшие бояр и слуг княжеских, были красивее, чем корабли простых воинов, Олег, заключает предание, возвратился в Киев с золотом, дорогими тканями, овощами, винами и всяким узорочьем; народ удивился такому успеху и прозвал князя "вещим", то есть кудесником, волхвом.