Some went on and fully converted. There were also a series of attempts to proselytize to the Icelanders. Around 980, a converted Icelander called Þorvaldr Konráðsson inn víðförli ("the far-traveling") brought back a German bishop named Fridrek, but was mocked and wound up being involved in two men's deaths and having to leave the country again in haste. Then King Olaf Tryggvason, who was violently pushing Xianity in Norway, sent another converted Icelander, Stefnir Þorgilsson. He started destroying vés and god-images and was declared outlaw; moreover the Althing passed a law on "kin-shame" (frændaskömm) requiring families to prosecute Xian members who blasphemed the gods. King Olaf tried again with a priest called Þangbrandr, who had experience converting people in the Faroes as well as Norway. He was in Iceland roughly from 997 to 999 and managed to convert some prominent men, but in the process he killed two or three for making mocking verses about him and he returned to Norway with a less than satisfactory report.

The king then put the screws on. He forbade Icelandic ships to put in at Norwegian ports until the country converted, and for good measure seized and held as hostages several Icelanders who were in Norway at the time, including the sons of some important chieftains. There was consternation in Iceland - and redoubled agitation by the Xians there.

At the Althing the following year, 1000, Xians and heathens almost came to blows but both sides eventually agreed to accept the ruling of the Lawspeaker, Þorgeir Þorkelson, who held the goðorð of Ljósavatn. He "went under the cloak" (meditated under a fur) for a day and a night and emerged with the decision that Iceland was to become Xian, providing three conditions were met: Icelanders would continue to be allowed to eat horseflesh (banned by Pope Gregory III in 742 because of its use in Germanic rites) and to expose unwanted babies, and they could continue heathen worship in private if they wished. As a goði, Þorgeir had images of the gods in his charge; to demonstrate his commitment to changing religion on behalf of all Icelanders, he took them and threw them into the waterfall that is now called Goðafoss.

The Pope guaranteed the Icelanders their three exemptions in perpetuity, but of course once the church was established in the country they were withdrawn and superseded by the usual prohibitions.

Despite the conversion, Icelanders remained proud and determined to follow their own traditions. They resented Norwegian influence over their bishops and were hostile to bishops who tried to enforce church rules against, for example, concubinage; for almost two centuries goðar and their sons would hold positions as priests as if the goðorð were still a priestly position as it had been in heathenry; and they disliked monks and when monasteries were established, they were tiny and were not daughter houses of foreign monastic foundations.

It was this pride that led to the writing down of the eddic and skaldic poetry and the sagas. Most of the "family sagas" or "sagas of the Icelanders" (Íslendingasögur) were written down in the thirteenth century; the earliest seem to date to the late twelfth century. The poems we call the Elder Edda are preserved in a small manuscript called the Codex Regius that was copied in the second half of the thirteenth century, and in a fourteenth-century manuscript based on the same original. Snorri Sturluson, who is believed to have written both the Prose Edda and the historical sagas collectively known as Heimskringla, lived from 1178 to 1241; the Prose Edda successfully revived the art of skaldic composition by teaching the poetic techniques, the meters, heiti, and kennings, familiarizing Xians with the necessary lore of the gods to compose kennings, and reassuring them that they did not need to espouse heathenry to continue the tradition. It is hard to guess whether the Eddic poetry would have survived without this work and its success, but the twelfth and thirteenth-century dates explain why there are gaps in our knowledge of heathen practices, and why some of what the sagas say about heathenry seems to be extrapolated from Xian times. The family sagas claim to be entirely true, but contain some embellishments and an unknown amount of fiction. Later sagas, the "fantasy sagas" (Lygisögur, "lying sagas") are complete fiction. That we have the family sagas and the poetry as a result of local pride also explains why we know vastly more about Icelandic heathenry - however reliable the information - than about heathenry even in Norway or Denmark.