In light of his early affinity with music, Melodia decided to defy his father's plans, which were to have him finish school and pursue higher education. In 1963, alongside drummer-vocalist Walmir Lucena (aka Mizinho), Melodia started what would become a lifelong musical career. At the time, he took day jobs as a typographer, salesperson, counter attendant while also working as a nightclub musician. After dropping out of middle school, likely in 1964, Melodia spent his teenage years writing songs (never recorded) and playing Jovem Guarda and Bossa Nova hits with his newly-formed band "Os Instantâneos" ("The Swift Boys"; could be intended as a pun for "The Snapshots") alongside friends Manoel, Nazzareno and Mizinho. He was also in another band, "Os Filhos do Sol" ("The Sons of the Sun"); they would play whatever it took to fire up a party, often times by singing in impromptu made-up English. Soon, well-connected "morro" scene habitués, Tropicália-related poet Waly Salomão and journalist Torquato Neto brought Melodia closer to mainstream music industry. Over this period, he was a partner to vocalist Marquinhos Sathan, who went on to become a relatively successful singer a few years afterwards.