1958(昭和33)年2月、大阪商船の新造船「ほのるる丸」が門司港に寄港した際、当時の門司市長は処女航海を祝うため、門司の風師人形を贈りました。その後同船がノーフォーク港に寄港したおり、優雅な風師人形と旧門司市の様子が新聞に紹介され、これを見て感銘を受けた当時のノーフォーク市長は、ノーフォーク市の象徴であるロイヤルメイスの複製とメッセージを当時の門司市に贈りました。これが契機となり両市の気運が高まっていき、翌年、ノーフォーク市長から門司市と姉妹都市になりたいとの文書が届きました。
1959(昭和34)年7月14日、当時の門司市議会全員協議会において、この申し入れを受けることを決定し、この日付を姉妹都市提携日としています。現在6つある北九州市の姉妹友好都市の中で、最も古いタコマ市と同じ年に提携しており、二番目に長い交流の歴史があります。