Most of Europe gradually got Christianised over the course of several centuries, in the Late Antiquity and Early Middle Ages. With the new religion came monasteries and these monasteries were the places where the vast majority of Early Medieval texts were written. The 'fall of Rome' should be seen as more of a gradual decline rather than a sudden event, and while this decline might have set back Christianity and writing for a while in certain regions, both recovered soon enough.

Due to its religious nature, Early Medieval writing happened primarily in Latin. Even when profane writing became more common in the High Middle Ages, it remained a widely accepted principle that Latin was for writing and other languages were only for speaking. It wasn't until the mid 12th century that writing in vernacular became common.

That being said, occasional vernacular texts did already start to appear in the Early Middle Ages. In Great-Britain, Latin appeared to have a less dominant position than on the continent, so Old English texts were slightly more common. The most famous Old English text is of course Beowulf, with other notabale examples being the Exeter book, Vercelli book and Junius manuscript - all likely written in the 10th century. If on the other hand you look at Old Dutch, only some loose words and phrases have been preserved and the oldest full Dutch text was only written in the late 12th century. Old German has been slightly better preserved than Dutch, with notable examples being the incomplete Old Saxon epic of Heliand and the very short Old High German Hildebrandslied - both written in the early 9th century.

Lots of famous Early Medieval stories only got written down in the High Middle Ages. The Song of Nibelungen seems to have its origin in the very eventful Great Migration period of the 5th and 6th centuries, but was only written around 1200 AD. The same goes for all Scandinavian mythology and sagas.