Complex sentence: In early 2005 the group finally started to record their debut album, with Rock-A-Bye being their first single.
Split into simpler sentences: In early 2005 the group finally started to work on their debut album. "Rock-A-Bye" was their first single.