W 2004 z utworem „Lane moje” zwyciężył w programie Evropesma 2004, dzięki czemu został pierwszym w historii reprezentantem Serbii i Czarnogóry w Konkursie Piosenki Eurowizji. 15 maja zajął drugie miejsce w finale konkursu organizowanego w Stambule. Po finale konkursu otrzymał Nagrodę Dziennikarzy im. Marcela Bezençona. Piosenka „Lane moje” została również nagrana w wersji angielskiej („Good Bye”) i wydana na singlu przez międzynarodową wytwórnię fonograficzną Warner Music. Po występie na Eurowizji podpisał kontrakt płytowy z agencją Minacord Production oraz zaczął pracować i komponować we własnym studiu nagraniowym. W sierpniu zagrał koncert w Marusi na południu Aten, gdzie odbywały się Letnie Igrzyska Olimpijskie 2004. W tym samym roku nawiązał współpracę z Dino Merlinem, z którym napisał i nagrał piosenkę „Superman”. thumb|left|Joksimović i Jovana Janković podczas 53. Konkursu Piosenki Eurowizji (2008) W 2005 skomponował utwór „Jutro” dla Jeleny Tomašević oraz otworzył własną rozgłośnię radiową Radio Lane, a także wydał singiel „I Live My Life for You”, który nagrał w duecie z Tamee Harrison. W tym samym roku napisał też swoją pierwszą partyturę filmową, tworząc oficjalną ścieżkę dźwiękową do produkcji Ivkova slava, a także wydał album pt. IV (Ima nešto u tom što me nećes), który osiągnął wynik ponad 800 tys.