Prvi velik korak vokalne skupine Katrinas je prišel z odločitvijo za svoj prvi album. Tako je decembra 1999 pri ZKP RTV Slovenija izšla zgoščenka z naslovom Slovo tisočletju. Na njej so zbrane njihove najljubše priredbe tujih in slovenskih evergreenov, posnete z revijskim orkestrom Iuventus. Je plod večletnega sodelovanja s Tomažem Habetom, aranžerjem vseh skladb, avtorjem prevedenih besedil in dirigentom orkestra.