Young Kostas lost his father when he was three months old and the hardships that his family encountered probably shaped his later life. He was unable to complete his secondary education and instead was drawn to the lyra - the main musical instrument in that part of Crete. After much practice, Moundakis became an accomplished player and was soon teaching others the art of playing it.
Throughout the 1960s, Moundakis made a name for himself by writing and/or singing the best-known Cretan songs of that era: "Ο Πραματευτής" (The traveling salesman), "Δεν έχω άλλα δάκρυα" (I have no tears left), "Της ακρογιαλιάς νεράϊδα" (Nymph of the beach), "Η κότα η στρουμπουλή" (The plump chicken), "Ένα ματσάκι γιασεμιά" (A bunch of jasmins), etc. Many of those songs have been re-recorded by other artists including Nikos Xylouris.