立国之后，四方归附者逐渐增多。一日，朱蒙发现沸流水中有菜叶顺流漂下，细心的他据此而知上游有人居住，便以出猎为名前往探寻。果然，沸流水上游有一个名叫沸流的部落国家。朱蒙与该国国王松让进行了交涉，两人都要求对方做自己的附庸。于是，为了解决争执，朱蒙与松让进行了辩论和射术的比试，结果朱蒙胜出。次年，松让以其国归附朱蒙……到朱蒙去世前，高句丽又征服了荇人国、北沃沮等部落国家，其国力一步步地增强。

实际上，以上内容大多是史学家对朱蒙的个人英雄主义式的记述，仅凭自身及几个助手的力量，是决不能建立起一个较为强大的部落国家的。根据学者的分析，跟随朱蒙出走的乌伊、摩离、陕父实乃三个小部族的代称，身着麻衣、衲衣、水藻衣的三人亦然；至于沸流国的归附，那应当是部落间联姻的结果。可见，最初的高句丽国家是通过结盟、联姻、武力征服等途径形成的诸多地缘部落的联合体，高句丽族是由夫余、沸流、北沃沮等族组成的共同体，而朱蒙所部则是这个联合体、共同体的中心。

鲤鱼救国

朱蒙建国后，高句丽便接受了西汉帝国的册封，成为东北边疆内的封国。高句丽族生活在玄菟郡（相当于今辽宁东部、吉林南部部分地区和清川江以北地区）境内，于是，汉朝统治者便通过玄菟郡政府定时赏赐给他们相应规格的朝服和乐队仪仗，制作、掌管他们的户籍，而高句丽人则将果下马（一种罕见的马匹）、貊弓等民族特产进贡给朝廷。但是，到了王莽篡汉时期，这种友好交往被打断了，取而代之的是中原统治者对边疆民族的歧视、压迫。结果，高句丽族汇入到了全国各地反抗暴政的武装斗争之中，与此同时，它的势力开始迅猛增长。到了朱蒙之子琉璃王类利（公元前19年—公元18年在位）统治后期，高句丽族不仅征服了周边的一些民族部落，甚至将汉民族势力赶出了玄菟地区。

高句丽民族国家会继续迅猛发展下去吗？历史说明了一切。东汉帝国建立之初，刘秀忙于统一内地，无暇经营边疆，同时，高句丽统治者开始盲目自大，不仅没有归附新生的东汉政权，反而加快了向周边地区扩张的步伐。这种紧张的边疆态势引起了东汉政府的关注，最终，东汉统治层决定出兵征讨。公元28年，由汉辽东太守率领的远征军进入了高句丽地区，这支军队十分齐整、雄壮，一路势如破竹，很快便逼近了高句丽的都城尉那岩城（琉璃王时期迁都至此，位于今吉林集安境内）。

兵临城下，高句丽的统治者们大武神王无恤（琉璃王之子，公元18年—公元44年在位）紧急召开了高层会议。大臣乙豆智献策说:“今汉兵远斗，其锋不可当也。大王闭城自固，待其师老，出而击之，可也。”无恤采纳了他的建议，死守尉那岩城。但是，数十天过去了，汉军却只围不攻。城内的水粮供应越发不足，军民的士气也越来越低落，尉那岩城随时都有被攻破的可能。于是，焦急的无恤再次向乙豆智问策。乙豆智头脑冷静、聪慧过人，他分析说:“汉人说我国是岩石之地、没有水泉，于是长期围困，想乘我们困绝之时来攻城。王宫的水池中有不少鲤鱼，我们可以用水草将它们包裹好，连同美酒送到汉军营中，以‘犒军’为名来麻痹对方。”无恤认为这是个好办法，便迅速差人去做，并附上了一封恭维汉朝的书信。汉将果真被这些新鲜的“慰问品”迷惑了，他们认为城中有充足的水源，短时间内难以有所行动；再者，劳师远征，自己的后勤补给也难免出现问题，对方既然已经奉上了言语恭顺的书信，班师回朝也有了交代。于是，在宣扬了浩浩皇威之后，大汉军队撤回了塞内。就这样，靠着一只只鲜活的鲤鱼，高句丽避免了亡国之灾。

据《三国志·魏书·东夷传》记载，高句丽人“性凶急，喜寇钞（抄）”。或许正是这样的民族性格决定了高句丽不会是一个“安分守己”的边疆封国。

“鲤鱼救国”之后不久，高句丽便派遣使者到东汉朝贡并接受了册封。此后，它与汉朝的关系时近时远、时好时坏，在太祖大王宫（公元53年—公元146年在位）、新大王伯固（公元165年—公元179年在位）时期，双方甚至一度战事频繁，但是，高句丽却始终没有放弃汉朝的封号，不忘与汉朝修好。

纵观高句丽民族国家的早期历史，就会发现它与中原王朝既有着友善而广泛的交流，同时双方也曾发生过摩擦、战争。不过，无论是高句丽对边疆地区的侵略，还是中原政权对它的征讨，都属于中国古代的民族内部问题，高句丽民族国家的封国地位是无法改变的。