In 2003 Maimon signed up for the auditions of the first season of the then-new singing talent show "Kokhav Nolad" (Tzvika Hadar, the host of the show and one of the judges during the auditions stage, removed himself from judging her audition due to their previous acquaintance). She passed the auditions and made it to the show team. In the head-to-head stage of the show, Maimon sang "Atuf BeRahamim" (Covered With Mercy) by Rita, and passed to the semi-finals. Maimon participated in the first semi-final, where she sang "Kshe’at Atzuva" (When You’re Sad) by Amir Benayoun, and won the first place, which secured her participation in the final. In the big final, that took place at the music festival in Nitzanim, Maimon sang "Don Quixote" by Dana International and finished in the second place, receiving more than 400,000 votes.