平城京や平安京の木簡によれば、武蔵国や相模国で?が生産され、貢物として都に送られていた。平安時代中期の『延喜式』の記述からは、?が固形物である点、保存がきく点、乾燥した品である点、升などの容積で計った点などが分かる[20]。『延喜式』には?の製造法も記録されており、大豆と海藻を素材にしている。この?は、現代の糸引き納豆に近いとする説もある[21]。なお、「塩?」のほかに「淡?」という名のものがあったらしいが、これは平安時代以降に姿を消している[22]。

納豆という語句が確認できる最古の書物は、11世紀半ば頃に藤原明衡によって書かれた『新猿楽記』である。同作中に「腐水葱香疾大根舂塩辛納豆」という記述があり、平安時代には納豆という言葉が既に存在していたことが確認できる。この記述の読み下しには諸説あるが（「舂塩辛」「納豆」、「舂塩」「辛納豆」、「大根舂」「塩辛納豆」、「辛納豆＝唐納豆」など）、これが糸引き納豆を指すのか、または塩辛納豆を指すかなどについて複数の解釈がある[23]。

北宋や南宋に渡航した仏教僧たちが塩辛納豆を持ち帰り、再度国内に紹介した。寺院内でも盛んに生産したことから、これらは寺納豆とも呼ばれるようになった。こうした伝統を持つものが今でも京都の大徳寺（大徳寺納豆）、天龍寺、一休寺や浜松の大福寺などで作り続けられており、名物として親しまれている。このうち浜松地方で作られる塩辛納豆は浜納豆の名称で販売されている[19]。

南北朝時代、丹波山国荘の常照皇寺にいた光厳法皇が村人に藁包納豆（山国納豆）の製法を伝えた記録が残る[24]。室町時代になると、糸引き納豆が広く知られるところとなり、日常食として消費されるようになるとともに、「納豆」という言葉もまず糸引き納豆を意味するように変化していったとされる。「納豆」の語で糸引き納豆を指したことが明らかな史料で、現存する最古のものは、15世紀の御伽草子『精進魚類物語』である[12][25]。文中に、納豆を擬人化した武士「納豆太郎糸重」が登場する[26]。他方で、主に調味料として用いられた塩辛納豆は、味噌にとって代わられるようになった。

戦国時代において、武将のたんぱく源やスタミナ源ともなっていた。
近世

日本を訪れたイエズス会の宣教師が作った『日葡辞書』（1605年）には、「Natto（納豆）」や「Natto jiru（納豆汁）」も収録されている[27]。料理書である『料理物語』（1635年）には、納豆汁に入れる具材として青菜や小鳥の肉、吸口としてカラシ、ユズ、ニンニクを挙げている[28]。

江戸時代では、京都や江戸において「納豆売り」が毎朝納豆を売り歩いていたが、製法は容器に付着した納豆菌による自然発酵で行われていたため、不安定であったと考えられている[24]。江戸時代後期の風俗や事物を記録した『守貞謾稿』には納豆について書かれており、大豆を煮て熟成させて作るとあり、醤油をかけて食べたり納豆汁として食べていた。江戸時代の風俗事典『人倫訓蒙図彙』に書かれた納豆売りは、叩納豆と呼ばれる叩いて平たくした納豆を青菜とともに売っており、手早く納豆汁が作れるように工夫されていた[29]。

納豆は9月以降に売られる季節商品だったものが、次第に時期が早まって1年中売られるようになった。また、自家製の納豆が多かった頃は田畑の畦で畦豆と呼ばれる豆を育てて納豆の材料にしていた[注釈 3][30]。
近代以降

朝に納豆を売り歩く商売は、明治以降も続いた。学生、女性、老人が納豆売りになった他、子供が学校に行く前に働いて収入を得られる仕事でもあった[注釈 4][32]。筆者未詳の『納豆考』（1873年-1883年）によれば、当初はザル（笊）に入れて笊納豆を売っていた。東京で納豆を売る際には、問屋から納豆を仕入れる他に、ザルを銭貨400文で借り、納豆を計る小升を銭200文で借りた。