Koukoudeas was born in Üstrümce, then part of the Ottoman Empire (now Strumica, North Macedonia) at the end of the 19th century.

After graduating from the Greek school in his hometown, he travelled to Athens in 1905 to escape the Bulgarian attacks and to be enrolled in the armed groups being gathered for the Macedonian Struggle.

On February 14, 1907, the united Greek bodies under Demestichas, Evangelos Koukoudeas, Nikolaos Zafeiriou from Chalkidiki and several other Macedonian and Cretan soldiers active in the Lake started from Tsekri (modern Paralimni, Pella) and attacked the Komitadji K. Delithanasis, in Bozej (modern Athyra, Pella).

Ioannis Demestichas wrote about Koukoudeas (translation from Greek):[3] Before the Balkan Wars, during the Italo-Turkish War (1911-1912) while the Italians had occupied the Dodecanese, he went to Icaria and helped Ioannis Malachias in the revolution against the Ottomans in July 1912, that set up the Free State of Icaria to prevent the island from being occupied by the Italians He then created a group of Icarian volunteers for participation in the First Balkan War and disembarked in Chios on 14 December 1912, where he took part in the Battle of Volissos and the Battle of Aipos during the Greek occupation of the island.

During the World War he fought as a reserve infantry officer, and was eventually commissioned into the Hellenic Army as a second lieutenant.