Moyal attended the auditions for the second season of Kokhav Nolad, and was chosen to participate in the show. He went on to win the competition, performing in front of 7,500 people at the season final, broadcast on August 15, 2004, from the Coca-Cola Music Village at the Hof Nitzanim. Harel Moyal won the contest with 862,368 votes, ahead of Harel Skaat in second place with 806,292 votes and Adi Cohen in third with 254,926.
Following his success in Kokhav Nolad, he participated in and won the 2004 Chanukah Song Festival, singing the song "Zorro", written by Uzi Khitman and composed by Shlomi Shabat.
He released his self-titled debut album in September 2005. The first single released from the album was "Middle of the Night in the Village", which he wrote about his experience of military service. The album was certified gold, selling over 20,000 copies in just over a week after its release.
In 2005, Moyal was cast in the lead role of a musical play called Like in A Movie, which began performances in February 2006. His second album, Levadi, was released in 2007.