Una storia sull'origine del nattō lo attribuisce al samurai Minamoto no Yoshiie (1039–1106), che partecipò a una campagna nel Giappone nordorientale tra il 1086 d.C. e il 1088 d.C. Un giorno, le sue truppe furono attaccate mentre facevano bollire la soia per i loro cavalli. Prepararono in fretta i fagioli e aprirono i sacchi di paglia solo pochi giorni dopo, quando ormai i fagioli avevano fermentato. I soldati li mangiarono comunque e ne apprezzarono il gusto, quindi ne offrirono un po' a Yoshiie, anche lui a cui piacque il gusto. Un'altra storia riguarda il principe Shotoku (574–622), che si dice abbia avvolto gli avanzi dei semi di soia bolliti in sacchi di paglia per il suo cavallo. Poiché le persone mangiavano questi fagioli fermentati e li trovavano deliziosi, questo tipo di fagioli filamentosi fermentati guadagnò presto popolarità in Giappone grazie al suo gusto unico e al sapore forte.