Konieczność ich pozyskania zapisano w planie zamówień prototypów nowych samolotów na rok budżetowy 1938. 18 kwietnia 1938 r. skierowano wstępną propozycję opracowania łodzi latającej do firmy Kawanishi, a bombowca lądowego do firmy Nakajima. Do wykonania nowej łodzi latającej wybrano firmę Kawanishi, ze względu na jej ogromne doświadczenie w projektowaniu i budowaniu tego typu samolotów, a sukces H6K tylko to potwierdził. Oficjalne zlecenie dotyczące opracowania projektu i budowy prototypu łodzi 13-Shi Taitei zostało przekazane tej firmie 21 sierpnia 1938 roku. Nowy samolot, oznaczony H8K, a nieoficjalnie nazwany 4-hatsu Ogata Kogeki Hikotei (4-slinikowa wielka uderzeniowa łódź latająca), miał mieć o jedną trzecią większą prędkość maksymalną, o połowę większy zasięg i dwukrotnie większy udźwig uzbrojenia niż H6K. Prędkość maksymalna miała wynosić co najmniej 444 km/h, prędkość przelotowa 296 km/h, zasięg w misjach rozpoznawczych 7400 km, a w misjach bombowo-torpedowych 6500 km. Miano wzmocnić uzbrojenie obronne, w porównaniu do H6K2, do pięciu działek kal. 20 mm i kilku karabinów maszynowych. Udźwig uzbrojenia bombowego zwiększono do 2000 kg. Mogły to być bomby różnych wagomiarów lub dwie torpedy Typ 91.