行長の生い立ち
永禄元年（1558）、行長は大坂・堺の豪商だった小西隆佐の子として京都で生まれ、若いころにキリスト教の洗礼を受けました。洗礼名はアゴスチイノといいます。初めは岡山城主・宇喜多直家に仕えましたが、天正8年（1580）頃から豊臣秀吉の家臣となりました。若い頃に頭角を現し、秀吉の水軍を率いて活躍したことから、イエズス会宣教師から「海の司令官」と呼ばれていました。
肥後南半国の領主として宇土へ
秀吉による九州平定後の天正16年（1588）、宇土・益城・八代などの肥後の南半分（約14万6千石）の領主として入国。宇土に本拠をおきました。最初は宇土氏や名和氏が居城した宇土城（西岡台）に入りましたが、翌年には現在の古城町に新たな城（宇土城〔城山〕）の築城を開始しました。
しかし、間もなく秀吉の命令で先鋒として2度にわたり朝鮮半島に出陣（文禄・慶長の役：1592～1598年）。文禄の役では、破竹の勢いで漢城（現在のソウル）や平壌を占領しました。一方、外交の責任者として朝鮮王朝や明との和平交渉も任されるなど、日本の命運を左右する重要な役割を担いました。まさしく「秀吉が日本を託した男」といえます。
新たな宇土城の築城
行長が築城した宇土城は、江戸時代に幕府の命令で2度にわたり破壊を受けていることから、どのような建物が建っていたかなど謎が多い城です。しかし、現在残っている城の形や発掘調査の成果、古文書の記述などから、往時の宇土城の姿をある程度明らかにすることができます。
宇土城は、幅約20ｍの水堀で囲まれた本丸（現在の城山公園）を中心として、二ノ丸や重臣たちが居住した三ノ丸を幅約30～40ｍの大規模な水堀で囲んで防御するとともに、本丸北側には水路で囲まれた家臣屋敷群が整備されていました。その範囲は東西約600ｍ、南北約900ｍにもおよびます。
また、本丸の北側には、緑川に通じる運河が存在し、有明海を通過する船が行き来したと考えられています。まさに「海の司令官」だった行長らしい城といえます。
城下町の整備
今日の宇土市街地の基礎がつくられたのも行長の時代です。宇土城とセットで一体的な整備がなされました。本町筋や新町筋沿いには商工業者が居住し、さらにその東側に物流の拠点だったと考えられる船場川や城下町を守る石ノ瀬城が配置されました。
このような宇土城下の町割り（都市計画）は、とても規格性が高く、博多の町割りと似ているとの指摘もあります。行長は宇土に来る直前、博多の町割り奉行の一人として博多の再興にあたっており、その時の経験が宇土城下町の整備に活かされたと考えられます。