高句麗という固有名詞に言及する最も古い記録は先述の通り『漢書』「地理志」に玄菟郡の首県として高句驪県が言及されているもので、玄菟郡の設置は前漢の武帝の時代、前107年である[2]。このため、どの段階を「建国」として扱うかという問題はあるものの、高句麗の政治的な結集は『三国史記』に記録されているよりも早い段階に行われたと考えられる[2]。
漢は日本海側へ続く流通路（玄菟回廊
）を確保すべく?貊の地に玄菟郡を設置した[2]。これを第一玄菟郡と呼ぶ[2]。最初に郡治が置かれた場所は、現在の北朝鮮の咸鏡南道咸興地方であると考えられている[2]。この時周辺地域を統治するために高句麗人の居住地を含む複数の地域に県城が置かれた。後に高句麗の首都が置かれる現在の中国領吉林省集安では、高句麗時代の王城の地下に土塁が確認されており、恐らくは高句麗県城であると考えられている[2]。同じく後に高句麗の首都がおかれる遼寧省桓仁にも、土城が確認されており、こちらも玄菟郡の県城であると考えられている[2]。この様に、漢は当初高句麗人の郡県統治を目指した[2]。だが、高句麗人は容易に服属しなかったと見られ、前75年には郡治を桓仁西北の永陵鎮に遷した[2][8]。これが第二玄菟郡である[2][8]。玄菟郡は旧来の高句麗県を廃止し、新たな郡治に高句麗県の名前を残した[9]。文献史学的には高句麗の興隆はこの前107年から前75年の間、概ね前1世紀前半頃であると考えられる[9][10]。一方、考古学見地からは高句麗の故地における新しい墓形式である積石塚の登場をもって高句麗のはじまりとするのが一般的となる[10]。積石塚とは、各種の石を積み上げ、中央に埋葬主体を儲ける形式の古墳であり、しばしば平面プランは方形となるものである[10]。具体的な年代割り当ては諸説あり、最も原始的な形態である無基壇式石槨積石塚のうち、あるものは紀元前3世紀に遡るとする説もあるがはっきりしない[11]。この形式の積石塚の中には五銖銭が出土しているものがあることから、紀元前後の時期までは遡ると思われる[11]。高句麗の最初期の中心地は卒本（忽本とも、現在の遼寧省本渓市桓仁満族自治県）のある渾江流域から集安のある鴨緑江流域にかけての地域であった。高句麗人たちは那、または奴とよばれる多数の地縁的政治集団を形成し、各那集団には大加、諸加とよばれる首長層がいた[12]。こうした那集団は首長連合を形成していたと考えられ、『三国志』「魏志[注釈 1]」や『魏略』など中国の史書は有力な那集団として桓奴部、絶奴部、消奴部、灌奴部、桂婁部と言う五族（五部）の存在を伝えている[12][注釈 2]。
那集団の連合体であったと考えられる高句麗は、漢の郡県と抗争を繰り返した[15]。興隆期の高句麗の動向は主に中国の史料によって伝わる。西暦8年に漢の平帝を殺害し帝位を簒奪して新たに新王朝を開いた王莽は、高句麗を含む東夷諸族に新たな印綬を配布した[16]。この時従来まで王を名乗っていた高句麗の君主は高句麗侯へと格下げされた[16]。西暦12年に王莽が匈奴出兵のために高句麗侯?（すう）に出兵を命じた際には、?がこれに応じなかったために捕らえられて処刑されたという[16]。更に王莽は高句麗の国名を「下句麗」として卑しめた[16]。この?が名前と具体的な行動が伝わる最古の高句麗の人物である[17]。王莽が倒され光武帝によって後漢が開かれると、「下句麗」侯は西暦32年にこれに朝貢し、高句麗王へと戻された[17][15]。
その後、高句麗の勢力は拡張し、これに圧迫された漢の玄菟郡は再び後方へと移転した[18]。これを第三玄菟郡と言うが、具体的な移転先についての記録はない[18]。ただし、現代の研究によって移転は105年から106年頃、移転先は遼寧省撫順にある永安台古城とするのが定説となっている[18]。この移転の後も、1世紀ほどの期間にわたり、高句麗王の宮（太祖大王）、遂成（次大王）、伯固（新大王）らが繰り返し遼東、玄菟などを襲撃し続けた[18]。 2世紀末の黄巾の乱とその後の中央政府の統制力の低下によって後漢が分裂状態に陥ると、遼東地方では公孫度によって公孫氏政権が打ち立てられた[18][15]。一方の高句麗では高句麗王伯固の死後、その息子延優（山上王、在位：197年-227年）が即位したが、これに反発した兄の発岐は公孫氏を頼って延優に対抗し、卒本に息子を残して自らは遼東へ移り住んだ[19][15]。延優は公孫氏と発岐から逃れて南に移動し、古くからの重要拠点である国内城（集安）で「新国」を建てた[15][20][21]。この「新国」がその後の高句麗の歴史を担うことになり、国内城は高句麗の王都となった[15][20]。国内城は旧高句麗県の県城を居城として転用したもので、背後の山には緊急用の大規模な山城（丸都城、山城子山域）が築かれた[15]。山城の丸都城と平城の国内城とは一体となって王都を構成した[21]。その後の発岐とその息子の動向は不明である[20]。 高句麗は漢の滅亡の後に中原を支配した魏と結び、司馬懿率いる魏軍が公孫氏を討伐する際には援兵も出したが、公孫氏滅亡後間もない242年には延優の跡を継いだ憂位居（東川王[22]）が西安平を寇掠し魏と衝突するようになった[22][23][21]。
丸都城遷都と周辺諸国との戦い