Cyhoeddwyd albwm cyntaf Catatonia, Way Beyond Blue yn 1996 gan roi cyfle ehangach i bobl glywed y rîffs gitâr popaidd a'i llais swynol ac unigryw. Ei llwyddiant mawr cyntaf oedd y sengl 'You've Got a Lot to Answer For'.