Valhalla je zejména textovou adventurou, ovšem často text doprovází obrázky ukazující postavu a lokaci, ve které se zrovna nachází. Děj se odehrává hlavně v Asgardu a Midgardu a v případě, že postava hráče umře, tak se objeví i pekle - Niflheimu. Cílem hry je posbírat šest mystických objektů pro postup hrou. V průběhu hledání naráží charakter na různé postavy z norské mytologie (například různí bohové a bohyně, trpaslíci, draci, vlci či havrani) a může se rozhodnout, které z nich pomůže.

Hra má k pochopení psaného textu hráčem své limity, ale dokáže chápat i text o několika větách v případě, že je psán pomocí slov, kterým rozumí. Tato slova jsou napsána v manuálu ke hře.