Galija featured Nenad Milosavljević (guitar and vocals), Goran Ljubisavljević (guitar), Predrag Branković (bass guitar), Nenad Tančić (drums) and Branislav Stamenković (keyboards). Tančić soon left the band because of his mandatory stint in the Yugoslav army, and was replaced by Boban Pavlović, who would, during the following years, remain one of rare permanent members of the band. Initially, in addition to their own songs the band performed covers of songs by The Rolling Stones, Eagles, Pink Floyd, Genesis and other foreign acts. In 1978, with the new keyboard player, Zoran Stanković, Galija won the first place at the Gitarijada festival in Zaječar. At that time they used to appear on stage in 18th century uniforms. Several months after Gitarijada, they performed at the Subotica Youth Festival with Ljubodrag Vukadinović playing the keyboards. During 1978 they performed as the opening band on Smak tour, and at the end of the year they performed at the BOOM Festival in Novi Sad. In 1979 the band released their debut album Prva plovidba (The First Sail) through PGP-RTB record label to mixed reviews by the critics. However, the tracks "Avanturista" ("Adventurer"), "Gospi" ("To the Lady") and "Decimen" became first hits for the band. Nenad Milosvaljević's brother Predrag Milosavljević appeared on the album on vocals as a guest musician, and also wrote most of the album lyrics. The band went on a promotional tour, during which they performed in Niš on the amphitheater in the Niš Fortress, the concert featuring a chamber music choir. In 1979 the band also appeared on Bijelo Dugme's Rock Spectacle on JNA Stadium, on which they performed alongside Bijelo Dugme, Kako, Mama Rock, Formula 4, Aerodrom, Opus, Senad od Bosne, Boomerang, Prva Ljubav, Prljavo Kazalište, Tomaž Domicelj, Metak, Suncokret, Parni Valjak, Generacija 5, Siluete and other acts. After the festival, Ljubisavljević, Branković and Vukadinović left the band. The bass guitarist Zoran Radosavljević, the guitarist Dušan Radivojević and the keyboardist Nebojša Marković became the band's new members. In 1980 the band released their second album, Druga plovidba (The Second Sail). The album was produced by Gordi guitarist Zlatko Manojlović. The songs were composed by Nenad, and the lyrics were written by Predrag Milosavljević. Druga plovidba was the first Galija album to feature Predrag Milosavljević as the official band member. The band promoted the album in their homecity with a concert in Čair Hall. The concert featured guest appearance by Zlatko Manojlović. During