Í Landnámu er þess getið, að Freysteinn hinn fagri hafi numið Sandvík, Viðfjörð og Hellisfjörð og búið að Barðsnesi. Hefur Freysteinn valið bæ sínum nafn af landsháttunum, því að hann stendur að vallendisbarði á annesi einu litlu, er gengur í sjó fram nær hálfri mílu innar frá Horni. Það má ráða af ýmsu sem of langt yrði hjer upp að telja, að bærinn hefur þegar í landsnámstíð staðið þar, er hann nú stendur. En munnmælin segja nokkuð á annan veg frá, hver þar hafi fyrstur land numið, og hvar bærinn hafi verið reistur í fyrstu, eins og sjá má af sögu þeirri, er hjer fer á eptir.
Barði hjet maður, er nam Viðfjörð og Hellisfjörð. Hann tók sjer byggð innanvert við Rauðubjörg niður undan skarði því er Skollaskarð nefnist og kallaði bæ sinn Barðsnes . Það heitir nú Bæjarstæði. Vættur ein ill bjó sunnanvert í skarðinu. Bar hún þungan hug til Barða og þótti hann illur gestur í byggðum sínum. Einkum áttu þau í brösum saman út af selvíði á svonefndum Selasandi austanmegin Horns; vildi hvort um sig hafa veiðina óskerða. Deildu þau um þetta löngum og varð af fullur fjandskapur. Gjarnan vildi vætturin hafa fyrirkomið Barða, en fyrir sakir karlmennsku hans þorði hún aldrei á hann að ráða. En margar illar glettur gjörði hún honum. Barði var forn í skapi og fjölkunnugur, enda varðist hann lengi með framsýni sinni brögðum grannkonu sinnar. Þó kom svo að lokum, að hann sá ekki annað ráð vænna en að láta undan síga. Það var eina nótt að Barða dreymir að hann er úti staddur. Verður honum þá litið til fjalls og sjer, hvar dökkvan skýflóka dregur upp undan Skollaskarði; þykir honum þá undarlega bregða við, því að úr skýinu verður kona, feykilega stórvaxin, og bendir sú ógnandi yfir bæ hans. Hann hrekkur upp við drauminn, klæðist í skyndi og snarast á dyr. Sjer hann þá að skessan situr uppi á fellsbrúninni og er að bisa við að spyrna stóru stykki úr hömrunum. Barði grípur rekuspaða sinn og hleypur til fjalls. Það var jafnsnemma að hann stökk yfir túngarðinn og kletturinn sprakk. Greikkar nú karl heldur en ekki sporið, og í miðjum hlíðum mætir hann skriðunni. Stingur hann þá niður rekkunni og í sömu svipan staðnaði skriðan. Þykir enn mega sjá þess merki. Barði treystist nú ekki lengur að hafa byggð sína þar undir skarðinu. Segir sagan að hann hafi þá flutt bæ sinn þangað, er hann stendur nú og búið þar síðan til dauðadags.
Þótt Barði þannig þokaði burt frá byggðum grannkonu sinnar, ljet hún þó ekki af að gjöra honum nýjar skráveifur. Barði átti knörr einn mikinn og fríðan og hinn vandaðasta að öllum útbúnaði. Knörr þennan hafði hann til flutninga og við ýmsan veiðiskap; stýrði hann jafnan sjálfur, en 12 menn reru. Eitt sinn hafði hann slegið mikið af sel á selasandinum og sendi menn sína heim eptir knerri sínum; þeim gekk vel ferðin og færðu þeir Barða knörrinn suður fyrir Horn. Báru þeir nú selinn á skip, og var það því nær fullfermi; síðan reru þeir heimleiðis, en Barði stýrði. Sjá þeir þá að skessan stendur á Hornseggjunum og horfir á þá. Getur Barði þess til, að nú muni kerlu þykja hann hafa verið heldur stórtækur um veiðina. Þegar þeir koma norður fyrir Horn tekjur að vinda; draga þeir þá upp segl og sigla hliðvind inn með Móunum, er svo eru nefndir. En er minnst varði heyra þeir hvin mikinn, og í sama vetfangi skellur stóreflis roka í seglið og hvolfir skipinu. Drukknuðu þar flestir menn Barða, en sjálfur synti hann til lands og tveir eða þrír menn aðrir. Varð þá komið logn aptur. Þeir Barði vinda nú klæði sín og búast til göngu. En er þeir eru komnir innan til á Móana, sjá þeir hvar vætturin situr á utanverðum Rauðubjörgum, og rennur honum nú mjög í skap. Og jafnskjótt og hann kemur í færi, þrífur hann upp stein eigi alllítinn og snarar að henni. Hún stökk undan og tók á rás, en steinninn fló með fæti hennar og veitti henni ærinn áverka, þótt eigi brotnaði fóturinn. Barði hefur þá upp annan stein eigi minni og kastar eptir skessunni, því að hann var allreiður. Hún sjer að steinninn fer hátt og stefnir á höfuðið; verður henni þá það til ráðs að fleygja sjer flatri, og fló steinninn yfir hana. Kallar hún þá til Barða og segir: „Drep þú mig eigi, Barði sæll. Aldrei mun jeg framar leitast við að vinna þjer mein, ef þú gefur mjer nú líf“. Barði svarar: „Maklegust ertu þess, að jeg stytti þjer stundir, því að þungar búsifjar hefur þú veitt mjer og alla jafna setið um líf mitt; væri jeg löngu dauður, ef þú hefðir mátt þínum ráðum fram koma. Hef jeg því eigi skap til að þyrma þjer, að mig væntir að brátt munir þú byrja aptur á nýjan leik með vjelræðin og eigi halda orð þín við mig“. Hún svara: „ Svik þarftu eigi að óttast af mjer; mun jeg öllu betur kunna að halda orð mín en flestir yðar, mennska fólksins“. „´´A það skal þá hætta“, segir Barði: “en svíkir þú mig, skal jeg þjer óþarfur meðan jeg má“. Skessan heitir honum trú og hollustu og ljet þá Barði hana upp standa. Mælt er að þau hafi þá gjört þann samning með sjer, að skessan skyldi hafa fjórðung allrar veiðar á Selasandi og skyldi hvorugt á annað deila þaðan í frá. Skildu þau síðan með blíðu, og er ekki annars getið en að sætt þeirra hjeldist meðan bæði lifðu.
Þegar þeir Barði komu heim til bæjar, sjá þeir að knörrinn kemur inn fjörðinn og rekur hratt fyrir hvassri hafgolu, gengu þeir þá til sjávar og tóku á móti honum þar sem hann bar að landi.
Barði var búsýslumaður mikill og manna auðugastur að löndum og lausum aurum. Hann hafði útibú um Viðfjörð og Hellisfjörð og ljet stunda þar búsmala sinn, því að þar voru kostsælli hagar og útibeit góð á vetrum. Hann átti og Nes í Norðfirði og fleiri jarðir. Var hann talinn mestur höfðingi þar um firðina og allra manna vinsælastur, enda reyndist hann jafnan bjargvættur landseta sinna og annara er hans leituðu. Áður Barði andaðist, hafði hann mælt svo fyrir, að hann skyldi haugsettur í knerri sínum á þeim stað, er bezt mætti sjá um Viðfjörð og Hellisfjörð, svo að hann mætti litast um lönd sín. Kvað hann það ekki mundu saka búsæld manna. #En raski nokkur friði mínum og rjúfi haug minn til fjár, mun það varða heill hans og svo beggja fjarðanna“. – Miðja vegur milli Barðsness og Viðfjarðarbotns við bæ þann, er að Stuðlum heitir, er annes eitt lítið, sljett og grasi vaxið. Er þar víðsýnt mjög um fjörðuna. Á framanverðu nesinu var Barða orpinn haugur og fje lagt í að fornum sið. Heitir þar síðan Barðahaugur og tanginn Barðatangi.
Liðu nú svo aldir fram, að einginn þorði að grafa í hauginn og allir töldu Barða verndara byggðarinnar.
Svo var það eitt sinn, að bóndi nokkur úr næstu sveit flutti búferlum að Stuðlum. Hann var ungur og ófyrirleitinn og lítt trúaður á forna hluti. Henti hann mjög gys að átrúnaði þeim, er byggðarmenn höfðu á hauginum, og kvaðst brátt skyldu forvitnast um, hvort nokkuð væri þar fjemætt fólgið. Menn töldu það hina mestu fásinnu og löttu hann að fremja slíkt ódæðisverk. Hann skeytti engu fortölum þeirra og einn góðan veðurdag fer hann til með húskörlum sínum og tekur að brjóta hauginn. En er þeir höfðu verið að um stund, urðu undarleg viðbrigði. Himinn gjörðist dimmur o myrkur dró yfir fjörðuna; en þar var að sjá sem eldbjarmi, er bæja var von. Bónda varð litið heim til Stuðla og sá hann þá að hús öll loguðu. Hætta þeir þá greptrinum og skynda til bæjar. Þótti þeim þá kynlega bregða, því að í einni svipan var horfinn eldur og myrkur og sól skein í heiði sem fyr. Hurfu þeir þá aptur til haugsins og tóku til verka á ný. En ekki höfðu þeir lengi grafið er allt fór á sömu leið sem fyr; var nú myrkrið svartara og eldurinn bjartari enn áður; fylgdi þar með hvassviðri og hafrót svo mikið, að sjór gekk á land. Nú fjell bónda allur ketill í eld, og taldi hann það ráðlegast að hætta verkinu og láta haugbúa hvíla í friði. Þegar er þeir voru farnir frá hauginum, hurfu undrin sem fyr. Bóndi hugði eigi framar til hauggraptrar, en ólánsmaður var hann alla ævi síðan; flosnaði hann upp af búi sínu, hraktist til fornra átthaga og dó þar á sveit í eymd og volæði. Ekki er þess getið, að fleiri hafi orðið til að brjóta haug Barða.