由布岳の大蛇を退治した為朝は、肥後国（熊本県）へと旅を続けました。そこにいた有力豪族・阿蘇忠国（あそただくに）と仲良くなり、その娘・白縫姫（しらぬいひめ）を娶ることとなります。阿蘇忠国は平氏一門なので、為朝とつるむのは若干不可解な気もしますが、そのあたりの事情はよく分かっていません。
　熊本県内にも為朝ゆかりの地は多数あります。木原山（熊本市）という山には、「雁回山（がんかいさん）」という別名があるのですが、その由来は
「この山に為朝が滞在していた際、雁が為朝を恐れて山頂を避け、回り込んで飛んだため」
だというのです。
　さらに為朝は日向（宮崎県）や薩摩（鹿児島県）をも平定して、肥前国黒髪山へとやってきました。黒髪山とは現在の佐賀県武雄市・有田町にまたがる山です。
　黒髪山では、たびたび現れる大蛇が土地の人々を苦しめていました。「また大蛇かよ」と思ってしまいますが、当時の英雄譚には話のバリエーションが少ないのでしょう。仕方ありません。
　領主の後藤高宗（ごとうたかむね）の依頼により大蛇退治を引き受けた為朝は、さっそく黒髪山に向かいますが、なかなか大蛇は現れません。神のお告げによると、
「池の中に高台を設けて、そこに美しい女を人身御供として座らせておけば大蛇が現れる」
といいます。
　そこで高札を立てて女を募集しますが、なかなか危険を冒してまで大蛇をおびき寄せる役を買って出てくれる者はいません。
　唯一応じてくれたのが、後藤高宗の元家臣で、浪人となったまま３年前に死去した松尾弾正之助（まつおだんじょうのすけ）の娘でした。名を万寿（まんじゅ）といいます。万寿は困窮する家族を救うため、命を投げ出す覚悟で応募してくれたのでした。
　果たして、万寿が池の中に身をさらすと、水しぶきを上げながら大蛇が姿を現しました。為朝は大蛇の喉元に矢を放ち、見事これを退治しました。
　大蛇を退治した為朝は、さらに上峰（佐賀県上峰町）へと旅を続けました。ここには、為朝の居城があったと伝わっており、その名も「鎮西山城（ちんぜいやまじょう）」です。為朝は西部を支配するという意味の「鎮西八郎」を名乗っていましたから、鎮西山という地名から見ても、為朝がここに住んでいた可能性は十分考えられます。
　鎮西山には「五万ヶ池（ごまがいけ）」があり、為朝が五万もの討伐軍を撃破したことで付けられた名だといいますが、さすがにこれは創作でしょう。
　為朝伝説はこのくらいにして、いよいよ保元の乱に入ります。