鳥取県西伯郡所子村大字福尾(大山町)出身。農家に生まれる。1912.7.17(M45)海軍兵学校卒業(40期)。同期に宇垣纏(後に中将:20-1-8-18)、梅崎卯之助(後に大佐・著述家:17-1-13)らがいる。少尉候補生となり、'13.12.1少尉に任官。様々な要職を経て、'24.2.1(T13)少佐となり、'26.11.25海軍大学校を首席で卒業(24期)した。'29(S4)中佐、'30.12.1人事局員、'32.12欧米各国へ留学。
1933(S8)大佐となり、連合艦隊首席参謀となる。軍令部作戦課長、連合艦隊兼第一艦隊参謀長などを経て、'39少将。軍司令部第一部長から'42中将となり、太平洋戦争中は連合艦隊参謀長、第二航艦長官、第一南遺艦隊長官兼第十三航艦長官、第十方面艦隊長官などを歴任した。
戦略戦術の神様とまで言われ、日米開戦時の軍令部作戦部長として'43連合艦隊参謀長になるまで日本海軍の作戦の中枢にあった。しかし、本質的に洋上決戦主義の信念が抜けていなかったようで、山本五十六(7-特-1-2)長官の飛行機でハワイを攻撃する(真珠湾攻撃)に対して、福留は全艦隊がハワイ近海に押し出し全力決戦を熱望していた。山本死後連合艦隊長官になった古賀峯一(7-特-1-3)の要求によって参謀長となり、作戦を多く編み出し決行したが戦局が不利な状態であったため成功することはなかった。戦局は不利に推移し、連合艦隊司令部をパラオからミンダナオに移動することになり、その途中、長官機と参謀長機は低気圧に巻き込まれ、古賀長官は遭難殉職(海軍乙事件)、福留ら九名は海に放り出され、泳いでセブ島東岸に上った。そこで当地のゲリラ部隊に捕らえられたが、日本軍の討伐隊に攻撃中止と引き換えに手渡され東京に戻った。捕虜となり連行されていた時に、防水ケースに入っていた機密文書〔1944(S19)3月8日付「聯合艦隊機密作戦命令第七十三号」(Z作戦計画書と暗号関係の機密図書)を海中に投棄したがゲリラに回収されている。なお、この機密文書入手の法はすぐにマッカサーに連絡がいき、オーストラリアで翻訳して20部配布された。東京に戻った福留は海軍大臣官邸で澤本頼雄(10-1-10)ら6名の将官から事情聴取される。その後、第二航空艦隊司令長官としてシンガポールに進出、そこで敗戦を迎えた。
戦後は英軍戦犯として禁固三年、二十五年の復員。復員後、水交会理事長を務めた。著作に「海軍の反省」〔1951(S26)〕がある。