Джон Фастолф родился в Восточной Англии. Его отец был моряком. В 1401 году Джон отправился в Ирландию в свите Томаса Плантагенета, позднее герцога Кларенса, назначенного тогда наместником острова. В 1412 году сэр Джон последовал за Кларенсом во Францию, в следующем году он стал капитаном Вьера (Гасконь). Сопровождал Генриха V в походе 1415 года и был назначен заместителем Томаса Бофора, капитана Гарфлера. Со временем Фастолф поднимался по служебной лестнице — был назначен коннетаблем Бордо, а потом и наместником короля в Гиени. В 1419 году он был посвящен в рыцари.
