納豆が文献に登場する最古のものは「精進魚類物語」　といわれています。是は室町時代の作品だそうです。その文頭部分を下記に示します。

■精進魚類物語　東京大学図書館蔵
去ぬる魚島元年八月朔日。精進魚類の殿原は。御料之大番にぞ、参られける。遅く参をは、闕番にぞ、付けられる。
折節、御料は。八幡宮の御斉にて、放生会といひ。彼岸といひ。旁々、精進にてぞ、渡らせ給ひける。
越後の國の住人。鮭大助長ヒレ（原文は魚偏に枚の旁）が子ども。鮞の太郎ツブ（原文は魚偏に立）実。同次郎鮷吉。兄弟二人候ひしをは。遙の末座へぞ下さるゝ。爰に美濃國の住人。大豆の御料の子息。納豆太郎種成ばかりそ。御身近くは、被召ける。
鮭子共腹立。一箸申して、殿原に。味はゝせむとは思へども。親大助に申合てこそ。火にも水にも。入免とて。クチナシ（原文は木偏に梨）色狩衣着て。款冬井手里へぞ、被帰ける。
其日も暮れぬは。駒に鞭棒。夜を日について、打程に。同八月三日、酉已点には。越後國の大河郡。鮎の庄、大介の館に、下着す。
兄弟、左右に相並び。畏て申。我等、此間、大番の勤仕の上洛、仕て候へども。大豆の御料の子息。納豆太郎に、御意を移し。目も懸られず。
剰、及恥辱、末座に被追下候し間。当座にて、何にも成。火にも水にも、入はやと、存しかとも。如此の子細をも申合てこそと、存候間。是迄、下向申ける。（以下略）

■精進魚類物語　神宮文庫蔵
祇園林の鐘の声、聞ば諸行も、無常也、沙羅双林寺の蕨の汁、生死、ひつすひしぬへき、理をあらはす、おこれる炭も、久しからず、美物を焼は、灰となる、猛き猪も、遂には、かるもの下の塵となる
遠く異朝を、たつぬるに、獅子や象、豹や虎、これらは皆人主の政にも随はず、あるときは人を損し、ある時は獣を害せしかは、遂には、ひとの為にも、とらわれ
又近く、本朝を尋るに、山の狼、里の犬、ことひの牛の、そらたけり、荒たる駒のいばえ声、これらは皆、とりとりなるといえども
まちかくは、越後國、せなみあら川、常陸國、鹿嶋なめかた、凡、北へ流る河を、領知しける、鮭の大介鰭長か有様を、伝へうけ給るこそ、心も詞もおよはれね
去る魚鳥元年壬申八月一日、精進魚類の殿原は、御料の大番にぞ参りける、遅参をば、闕番にこそ、付られけれ、折ふし、御料は御斎玲礼にて、放生会といひ、彼岸といひ、かたがた御精進にてそ、渡らせ給ひける
こゝに、越後國の住人、鮭の大介鰭長が子供に、鮞の太郎粒実、同次郎弼吉とて、兄弟二人、候ひしおば、遙の末座へぞ下されける
こゝに美濃國住人、大豆の御料の子息、納豆太郎糸重ばかりをそ、御身近くは、めされける（以下略）

京都故事　-京の味（http://www.ne.jp/asahi/kiwameru/kyo/k-koji2.htm）　の普茶料理のコラムに精進魚類物語の紹介があります。

以下引用

室町時代のお伽草子に『精進魚類物語』がある。
魚鳥元年八月一日、米の御料の大番にめされた越後国の住人鮭の大介鰭長の嫡子ハララゴ（魚へんに而）の太郎粒実は遥かの末座にすえられ、美濃国の住人大豆の御料の子息納豆太郎糸重のみがおそば近くに召された。
遺恨に思った粒実は帰国して魚類一同を集めて、精進類をせめた。
いっぽう精進方も軍勢を集め大合戦におよび、魚類は利あらず鍋の城にこもって討死したというものである。
このとき精進方にはせ参じたものに蒟蒻兵衛酸吉、牛蒡左衛門長吉、茗荷小太郎、味噌冬近、蕎麦大隈守、蓮根近江守、芋頭大宮寺、昆布大夫、柚皮庄司などがあり、其勢五千余騎に達したと記している。

以上

上記東京大学図書館蔵書では「鮭大助長ヒレ（原文は魚偏に枚の旁）」ですが、神宮文庫蔵書では「鮭の大介鰭長」とナガヒレがヒレナガ、同様に「納豆太郎種成」は「納豆太郎糸重」とタネナリがイトシゲとなっています。「京都故事」後者（の系統）を参照したものと推測します。