Aufgrund der besonderen Lage, der Nähe zu Korea und dem Festland von Asien, wurde bereits sehr früh hier gesiedelt. Die ältesten Funde deuten auf einen Gründungszeitraum um 300 v. Chr. hin. Fukuoka wird deshalb auch die „Wiege der japanischen Zivilisation” genannt. Seit dieser Zeit unterhielt die Stadt enge Handelsbeziehungen zu Korea und zum Kaiserreich China, wie z.B. ein goldenes Siegel (auch bekannt als Kin-in) des Kaisers Ho der Han-Dynastie beweist. Dieses Siegel wurde 57 nach Christus übergeben. Weitere Funde, wie z.B. ein Gästehaus aus dem 9. Jahrhundert, belegen auch weitreichende diplomatische Beziehungen zum asiatischen Kontinent. Die Stadt hieß damals noch Hakata.
Zu Beginn des 17. Jahrhunderts wurde eine zweite Stadt rund um das neu gegründete Schloss Fukuoka gegründet. Im Laufe der Zeit wuchsen beide Städte mehr und mehr zusammen bis sie 1889 unter dem Namen Fukuoka vereinigt wurde. Der Hauptbahnhof der Stadt heißt heute noch Hakata.
Obwohl die Stadt große Schäden durch den Zweiten Weltkrieg erlitt, blieb Fukuoka die wichtigste Handelsstadt auf Kyūshū.