I read Íslendingabók and Kristni Saga: Book of the Icelanders and Saga of the Conversion, and at one point it says, that after Olaf Tryggvason became the king of Norway and was in the process of converting Norway to Christianity, he was asked what they would do in place of the normal winter festivities. He discussed it with his personal priest and declared that they would hold a special mass for Christ and I believe a feast afterwards. It seams to imply that it was the first Christmas celebration. However I know that these books where written at least 100 years after the fact and it feels slightly like nationalist propaganda. Are there any records the detail the first Christmas or that mention and Christ's mass before Olaf's reign? (995-1000A.D.)
Are you really sure that Íslendingabók (written before 1133) mention the episode you described in OP? The famous chapter 7 of the work on King Olaf Tryggvason of Norway and the conversion of Iceland does not mention Christmas at all, I've double (actually thrice) checked.
AFAIK The oldest account that established the connection between Olaf Tryggvason and Christmas (in a Christian way) is Ágrip af Nóregskonungasögum (ca. 1190), Chap. 19:
'......He [Olaf Tryggvason] first raised churches on his own estates and he abolished paga:n feasts and sacrifices, in place of which, as a favour to the people, he ordained the holiday feasts Yule and Easter, St John’s Mass ale and an autumn-ale at Michaelmas [English Translation is taken from Driscoll (ed. & trans.) 2008 (1995): 31, 33]'
On the other hand, fragmentary references in Norwegian provincial law-books also confirm that the church authority in different Norwegian legal provinces impose the canonical observance of Christmas as a holiday or holidays on people by the 1st half of the 12th century, though they don't specify this custom with him.
To give a famous example, Clause 7 of Older Gulathing law, the lawbook from Western Norway, stipulates as following:
'We also promised that every husbandman and his wife shall join in an ale feast, all sharing equally, and bless it on Holy Night with thanks to Christ and Saint Mary for peace and a fruitful harvest (til Krist þakka ok sankta Mariu, til árs ok til friðar). And if this is not done, they shall pay a fine of three marks to the bishop. And if a man allows three winters to pass without giving this ale feast, and he is accused and convicted of this, or [if he fails to heed] the penalties that we have added to our church law, he shall have forfeited his goods to the last penny; and the king shall have one-half of it and the bishop one-half. But he has the choice of going to confession and doing penance; [then he may] remain in Norway; but if he refuses to do this, he shall depart from the king’s dominions' [English translation is taken from Larson (trans.) 1935: 40].
In addition to All Saints day, this law text specifies Christmas as well as St. Mary's day as occasions that the household should hold the communal ale fest (minimum 3 guests). Note that the scribe of Gulathinglaw, however, associates this passage with 'Olaf', but not Olaf Tryggvason, usually identified with St. Olaf (Olaf Haraldsson: d. 1030). Scholars agree in general neither on the exact provenance of this clause (from ca. 1022 to the middle of the 12th century) nor on how much pre-Christian Yule (jól) tradition was inherited here (Cf. Sanmark 2004: 229 note 7).
In short, we don't have enough trustworthy sources in our hand to illustrate what exactly early Christmas fest celebrated by Olaf Tryggvason like, based on the source texts (sorry).
Works mentioned:
+++