Í Landnámabók kemur Grímsey ekki við sögu. Bókin var líklega skráð um tveimur til þremur öldum eftir lok þess tíma sem er kallaður landnámsöld og er vafalaust að talsverðu leyti reist á arfsögnum, en ekki er hægt að treysta því að hún fari alls staðar með rétt mál um landnám. En sennilegast verður að teljast að fólk hafi ekki sest að í Grímsey í upphafi byggðar á Íslandi. Eyjan hefur líklega þótt of afskekkt, meðan nóg landrými var í boði á meginlandinu. Frá 19. öld eru til þjóðsögur um landnámsmanninn Grím sem byggði í Grímsey, en þær eru sjálfsagt sprottnar af nafni eyjarinnar.
Hér má sjá söguskilti um Grímsey
Í Íslendingasögum kemur Grímsey við nokkra atburði sem eiga að gerast á áratugunum um aldamótin 1000 og er það jafnan tengt nytjum af eyjunni, svo sem rekum og útræði þaðan. Í einni sögu, Valla-Ljóts sögu, segir að róið hafi 30 skip frá eyjunni. Aldrei er minnst á fasta byggð þar í þessum sögum, en í Ljósvetninga sögu er þó nefndur "Grímseyingr einn, ungr ok fráligr", sem sóttist eftir heimasætu á Tjörnesi. Í Heimskringlu er saga af því að Ólafur Haraldsson Noregskonungur sendi hirðmann sinn, Þórarin Nefjólfsson, til að biðja Norðlendinga að gefa sér Grímsey. En Einar Eyjólfsson Þveræingur kom í veg fyrir það með ræðu sem hefur lengi verið í minnum höfð. Í þessari sögu, sem á að hafa gerst upp úr 1020, er sýnilega gert ráð fyrir að eyjan sé óbyggð en nytjuð af Norðlendingum.
Tveimur öldum síðar virðist komin föst byggð í Grímsey. Árið 1222 hrökklaðist Guðmundur biskup Arason þangað með lið sitt eftir að menn hans höfðu drepið Tuma, son Sighvats Sturlusonar, héraðshöfðingja í Eyjafirði. Sighvatur og Sturla sonur hans sóttu biskup í eyna og sigruðu menn hans í bardaga. Í tengslum við þá atburði er talað um kirkju og kirkjugarð í Grímsey. Í sögu Arons Hjörleifssonar, eins af fylgdarmönnum biskups, segir frá manni sem Gnúpur hét, "er þá bjó í Grímseyju ok var inn mesti maðr at mannvirðingu af bóndum." Tveimur áratugum síðar börðust "Ketill Gnúpsson ok þeir Grímseyingar" með Kolbeini unga Arnórssyni í Flóabardaga og "höfðu enn mikit skip."
Á 19. öld var skráð sögn um hvernig byggð hófst í Grímsey. Þar segir að lengi hafi engum verið leyft að setjast þar að vegna þess að eyjan hafi þótt svo gagnsöm til eggjatekju og annarra hlunninda. Svo hafi hópur Þingeyinga sest þar að í leyfisleysi og byggt sér bæi. Þegar vermenn komu þangað úr Eyjafirði vörnuðu eyjarskeggjar þeim landgöngu og felldu þá alla í bardaga.
Ómögulegt er að dæma um sannleiksgildi þessarar sögu. En ásókn fólks að hefja fasta búsetu í Grímsey hefur vafalaust aukist eftir því sem fólki fjölgaði í landinu og minna varð um jarðnæði. Af þessu fara engar áreiðanlegar sögur, og því getur hver og einn ályktað það sem honum þykir sennilegast.