初代王の鄒牟（朱蒙）について伝える記録には『広開土王碑文』『魏書』『三国史記』がある[268]。これらの記録は細部は異なるものの、夫余（扶余）の地から逃れた高句麗の始祖鄒牟（朱蒙）が大河を渡って南の地に高句麗を建国するという大筋は一致する[268]。この神話は高句麗と夫余の同族性の根拠ともされるが、現代の学者は基本的に後代の創作であるとし、史実としては扱わない[269]。また、東明王の名は『論衡』や『三国志』「夫余伝」引用の『魏略』には夫余の建国者として登場する。この東明（聖）王と朱蒙の説話は元来別々の神話であったが、後に高句麗の夫余征服との関わりから（ある程度は政策的に）同一視されるようになったものであるという説が現在有力な見解の1つとなっている[注釈 24]。

武田幸男は『三国史記』記載の高句麗の王系をその諡号や葬地の分類から以下の通りに分類している。
伝説王系：初代東明聖王（朱蒙）から第5代慕本王まで。『広開土王碑文』『魏書』『三国遺事』などにそれぞれ独自の系譜が伝わる。

大王王系：第6代太祖大王から第8代新大王まで。大王号を持ち、中国史書に由来する諱を持つ（大祖大王：宮、次大王：遂成、新大王：伯固）。また新大王以外の葬地が伝わらない。

丸都・国内王系：第9代故国川王から第19代広開土王まで。初期の王に中国史書との整合を取る過程で誤って追加された王を含む可能性があるが、全体として史実性が認められる。

平壌王系：第20代長寿王から第28代宝蔵王（宝臧王）まで。全て実在の王からなる。

このうち建国神話に伴って造作された伝説王系の王たちについては『三国史記』の他、『三国遺事』「王暦」や『魏書』「高句麗伝」に記載があり、最初の3代については既に述べた通り広開土王碑文にも対応する王が伝えられている[270]。しかし伝説王系の5王の親子・兄弟関係についてはそれぞれが独自の系譜を伝えており、その世代関係の伝承は後代に至るまで安定しなかったと見られる[270]。

大王王系に分類される太祖大王、次大王、新大王については古くからその記録の信頼性を疑われている[271]。武田幸男はこの3王の系譜について、『三国史記』の原資料となった『海東古記』が編纂される際、高句麗の古記録と中国史書に登場する王との対応をとることができず、両者の形式的整合が試みられた結果生み出されたものであるとする[272]。

丸都・国内王系以降の王については原則的に実在していた人物の記録によると推定できるが、大王王系との結節点の王である故国川王と山上王については、『三国史記』にそれぞれ矛盾する系譜が伝えられている[272]。このため、故国川王の実在性が長く議論の対象となっている[273]。池内宏はこの王を架空の王と見、三品彰英は実在するとした[273]。

武田幸男によれば、まず『三国志』の記録を意識して高句麗の古記録の王系譜が作成され、次いでその王系譜を『後漢書』の記録と対照しつつ『海東古記』の系譜が作成された[272]。更にそれぞれの記録が『三国史記』に原史料として使用された[272]。そして、故国川王および太祖大王（国祖王）は相互に矛盾する記録の整合性を取る試みの中で、いずれかの時点で加上された王であると考えられる[274][注釈 25]。
王姓

初代朱蒙から5代目の慕本王までの5王は尊称として「解」（ha）が付されており、この語は「高」と共に高句麗の王家の姓として知られている[275]。解は音の共通性から太陽（ha）、訓義によって光（pur）と解釈できる[275][276]。この尊称はやがて中国風の姓のように扱われるようになり、伝説の王たちに共通する国姓として記録されるに至ったと見られる[275][注釈 26]。

高句麗王が「高」姓を用いた記録の初出は『宋書』「高句麗伝」に登場する高�l（長寿王）である[277]。この由来としては、早くから中華文明に接触していた高句麗が高陽氏・高辛氏の子孫として「高」姓とする付会を行なったとする見解や[278]、北燕王の高氏に由来するものとする意見がある[277]。
王と五部詳細は「高句麗五部」を参照

最も初期の記録では、高句麗人たちは那、または奴とよばれる多数の地縁的政治集団を形成していた[12]。各那集団には大加、諸加とよばれる首長層がおり、「加」は北部アジアにおける首長号であるカン（カーン、ハーン）と同様のものであるとも言われる[12]。2世紀から3世紀頃の積石塚は、これらの首長層と被支配層の間で築造規模の差が見られる[12]。こうした那集団は首長連合を形成していたと考えられ、『三国志』「魏志」や『魏略』など中国の史書は有力な那集団として桓奴部、絶奴部、消奴部、灌奴部、桂婁部と言う五族（五部）の存在を伝えている[12][注釈 2]。「魏志」によれば、当初の頃は消奴部から王（盟主）を出していたが、その後桂婁部から王を出すようになり、絶奴部は王妃を出していたという[12]。この那については氏族（clan）として捉える見解や[279]、「土地」の意味と解して部族（tribe）ないし原始的小国を指すとする見解がある[280]。

井上秀雄はこれら五族は一定の地域を地盤とする部族国家であり、初期の高句麗は部族連合の態をなし[281]、これらの部族はモンゴルのクリルタイのように王位継承に関わったとした[281]。また李成市は五族は王都に集住し王が統括したが、高句麗は族制的性質を強く残し王権は部族的制約を強く受けたとする[30]。『三国史記』は初期の高句麗の有力者について、しばしば出身部を明記している[注釈 27]。そして閔中王などのように、「国人による推戴」によって王位に就く例がしばしば見られる[282]。

高句麗の後期については、唐代の記録『翰苑』には高句麗に五部制度があり、これは『三国志』「魏志」や『後漢書』等の記述にある高句麗五部（五族）が改称されたものであるという記述がある[283]。それによれば元の高句麗五部（五族）は以下のように改称された[284]。

桂婁部：内部（黄部）

絶奴部：北部（後部/黒部）

順奴部：東部（左部/上部/青部）

灌奴部：南部（前部/赤部）

消奴部/涓奴部：西部（右部/下部/白部）

この情報の出元は『高麗記』であり[283]、同様の記述は唐の章懐太子による『後漢書』の注釈にもあるが[283][285]、その信頼性ついては長く議論の的となっている[286]。内部および東西南北または前後上下の方位部が実際に使われたことは、日本の記録にある高句麗人名に方位部が用いられているものがあることによっても証明される[287]。高句麗の制度と偶然一致する名称を日本側が適当に造作したとは考えづらいことから、これは実際に高句麗人が日本側へ向けてそのように名乗ったことによって記録されたと見られるためである[287][注釈 28]。

かつて池内宏や三品彰英は、唐代の学者が時間的隔たりを無視して『三国志』『後漢書』に記録された五部（五族）と唐代の高句麗の五部制度（行政区画、ないし官職制度）とを付会したものに過ぎず、本来この両者は相互に何の関係もないと論じた[286][289]。川本芳昭は両者を全く無関係とすることは一方的に過ぎると問題提起し[286]、匈奴の五部や百済の五部、および五方制、さらに燕（前燕、後燕）の官制とも比較しつつ、高句麗の五部制度は伝統的な五族（那集団）を背景に、極めて強力が隣国であった燕から導入されたものであると推定する[290]。