Do you mean in oral tradition, or in written form? Because if you mean in written form, there are loads of available options in Old Icelandic/Old Norse, in the form of fornaldarsögur and riddarasögur. These sagas - literally 'ancient stories' and 'knight stories' - contained elements of the fantastic and purely fictional.

A good example of a riddarasaga would be Viktors saga ok Blávus, about a fictional king of France and his magic carpet-riding buddy, who happened to be king of a far-off southern land. Thoroughly fictional and presented as fiction. Here's a good list of them, including some translations.

Insofar as fornaldarsögur, a good one would be Hrólfs saga kraka, which involved a character - Böðvarr bjarki, who might well be related to the character Beowulf - that could take the form of a bear in battle.

These sagas dealt with moral or ethical issues in clearly fantastical settings, and were not intended to be taken as literal events.