Narodil se v kalifornském městě Alameda. Jeho otec, Anthony Shuzo Fukunaga, patřil do třetí generace Japonců v Americe a narodil se v internačním táboře během druhé světové války. Jeho matka, Gretchen May (Grufman), má švédskou a americkou národnost, pracovala jako dentální hygienička a později jako asistentka na univerzitě v oboru historie. Po ní zdědil zájem o historii. Jeho rodiče se rozvedli a oba si našli nové partnery, s nimiž se vzali.

Původně chtěl být profesionálním snowboardistou, ale v dospělosti ho uchvátil filmový svět. Začínal jako kameraman a později se přihlásil na filmovou školu. Chodil na střední školu Analy a později absolvoval na Kalifornské univerzitě v Santa Cruz, kde v roce 1999 získal titul bakalář umění v oboru historie. Také chodil na Institut d'études politiques (IEP) v Grenoblu. Poté nastoupil na filmovou školu spadající pod New York University.

Trvale žije v New Yorku. Dříve dlouhodobě pobýval ve Francii, Japonsku, Mexiku a Londýně. Mluví plynně francouzsky a španělsky, naproti tomu vůbec neumí japonsky. Za svou mentorku pokládá scenáristku Naomi Foner, matku herců Maggie a Jaka Gyllenhaalových.