The group was formed in Zagreb in 1969. Their first successes came in 1976 when the composer Rajko Dujmić joined the band. That same year Novi Fosili played at the Split Festival, where their song "Diridonda" soon became a hit throughout the country. Their next several albums sold millions of copies and delivered many hits that are still aired on radios in Croatia today. The first female singer was Đurđica Barlović, in 1984 replaced by Sanja Doležal. The group's male vocalists were Vladimir Kočiš Zec and Rajko Dujmić.
Some of their hits include: "Za dobra stara vremena" ("For good old times"), "Milena", "Sanjaj me" ("Dream of me"), and many others. The band represented Yugoslavia at the 1987 Eurovision Song Contest. With their song "Ja sam za ples" ("I wanna dance") they reached respectable fourth place.
After the breakup of the former Yugoslavia, the group was disbanded, then gathered again, but without Doležal and Zec. It was disbanded again in 2001. Members of the most memorable lineup gathered again in 2005 for some revival concerts, and still working together.