Talið er að húsið Aðalgata 3 hafi verið reist árið 1906 fyrir Málfríði Möller sem var þá ekkja Möllers apótekara. Guðmundur Jónsson frá Narfeyri eignaðist húsið í kringum 1920 en það er ekki fyrr en um miðja tuttugustu öld að húsið fær nafnið Narfeyrarhús. Veitingarekstur hófst í húsinu árið 2000 og fékk það þá nafnið Narfeyrarstofa.
Húsið var upphaflega byggt sem íbúðarhús en ýmis starfsemi hefur verið í húsinu í gegnum tíðina. Árið 1996 festa Baldur Þorleifsson hjá Narfeyri ehf og Þorkell Þorkelsson kaup á húsinu og gerðu upp í upprunalegt horf. Ingibjörg Björnsdóttir keypti húsið 1999 og kom á fót kaffihúsi á neðri hæðinni en bjó sjálf á efri hæðinni. Árið 2001 keyptu, Sæþór H. Þorbergsson matreiðslumaður og Steinunn Helgadóttir, Narfeyrarstofu og gerðu að veitingahúsi á báðum hæðum. Árin 2011-2015 ráku Guðbrandur Gunnar matreiðslumaður og Selma Rut veitingastjóri veitingastaðinn þar til Sæþór H. Þorbergsson og Steinunn Helgadóttir tóku aftur við rekstrinum í desember 2015.