The recording of their debut album Maiden Voyage ( 2003 ) began .
In 2003 the band released their first album Maiden Voyage in Sweden .