[1] In 1995, she turned to jazz and released her first solo album for Blue Note, titled Cæcilie Norby.

Instead, she and Lan Doky arranged classic popular songs for a jazz line-up, like "Wild Is the Wind", "By the Time I Get to Phoenix" and a track by Curtis Mayfield on the first album, "The Look of Love", "Life on Mars", "Spinning Wheel" and "Set Them Free" by Sting on the second.

For both albums Norby also wrote lyrics to compositions by Randy Brecker, Chick Corea, Don Grolnick and Wayne Shorter.

[3] Her third album Queen of Bad Excuses, released in 1999, was a collaboration between her and Lars Danielsson, who already played bass throughout My Corner of the Sky.

With Ben Besiakov and long-time companion Lars Jansson on piano, Anders Kjellberg and Per Lindvall from Sweden alternating on drums with Billy Hart, who was also part of her debut recording, the line-up is accentuated by the guitar of John Scofield on more than half of the album, and saxophonist Hans Ulrik and Xavier Desandre Navarre on percussion.