Тапонім «Магілёў», відавочна, мае патранамічнае паходжанне — ад асабістага імя Магіла, якое ў сваю чаргу ўтварылася ад адпаведнай славянскай асновы[5]. Выказваліся таксама меркаванні пра сувязь тапоніма з канкрэтнай гістарычнай асобай — галіцкім князем Львом Данілавічам Могіем («Магутным Ільвом»), які нібыта збудаваў у 1267 годзе замак у сутоках рэчак Дубравенка і Дняпро (археалагічныя раскопкі не выявілі гэтага ўмацавання). Некаторыя даследчыкі лічаць, што назва Магілёва паходзіць ад імя князя полацкага Льва Уладзіміравіча (Льва Магутнага)[6].

Народнае паданне звязвае назву горада з імём асілка Машэкі, над магілай якога насыпалі вялікі курган, названы Магілай Льва (захавалася ўрочышча Машакоўка). Народны паэт Беларусі Янка Купала апрацаваў гэту легенду ў аднайменную паэму. Паводле «Запісак ігумена Арэста», у старажытнасці на месцы Магілёва быў стан разбойнікаў (іх атамана звалі Магіла) і шматлікія магілы забітых імі людзей, каля якіх узнікла вёска Магілка

Паводле археалагічных раскопак, старажытнае паселішча існавала на месцы Задубравенскага пасада яшчэ ў XII ст. Апроч таго, на гары Магіла мелася даўняе ўмацаванне[8]. У пач. XIII ст. Магілёў, відаць, быў цэнтрам феадальнай сядзібы-вотчыны і выконваў функцыі фартэцыі. У пачатку XIV ст. горад далучыўся да Вялікага Княства Літоўскага, дзе стаў цэнтрам воласці.

Упершыню Магілёў згадваецца пад 1267 годам у «Спісе гарадоў далёкіх і блізкіх», што датуецца канцом XIV ст., паводле якога горад нібыта залежаў ад віцебскіх князёў, таксама паведамляецца аб заснаванні горада галіцка-валынскім князем Львом Данілавічам, ад якога горад нібыта атрымаў сваю назву, але гэтыя звесткі неверагодныя. Імаверна, горад заснаваны ў 2-й палове XIV ст., больш ранняга матэрыялу археалагічныя даследаванні не выявілі, і на месцы будаўніцтва першага замка будаўнікамі быў выяўлены вялікі старажытны грунтавы могільнік — відаць, адсюль пайшла назва горада. У гэты час Магілёў знаходзіўся ва ўладанні каралевы Ядвігі, жонкі караля і вялікага князя Ягайлы. У 1431 годзе ён перайшоў да вялікага князя Свідрыгайлы, а ў 1503 — да вялікай княгіні Алены Іванаўны.

У XV ст. Магілёў быў адным з важных пунктаў на гандлёвых шляхах, што вялі з усходу на захад і з поўначы на поўдзень, тут мелася ўласная мытня. Пад 1447 годзе згадваецца праваслаўная Спаская царква. У пачатку XVI ст. горад увайшоў у склад Аршанскага павета Віцебскага ваяводства.

У сувязі з падзеннем Смаленска (1514) і пераходам яго на стагоддзе пад уладу Маскоўскай дзяржавы, многія тамтэйшыя купцы перабраліся ў Магілёў. Праз гэта яго ваколіцы неаднаразова (у 1518, 1519 і 1535 гг.) цярпелі ад рабаўніцкіх набегаў маскоўскіх захопнікаў, якія, аднак, самім горадам авалодаць не здолелі. У 1526 годзе скончылася будова новага замка. У 1561 годзе горад атрымаў права на войтаўства.

28 студзеня 1577 г. кароль і вялікі князь Стэфан Баторый надаў Магілёву поўнае Магдэбургскае права і першы герб. У велікакняжацкай грамаце зазначалася[9]: