Koukoudeas was born in Üstrümce, then part of the Ottoman Empire at the end of the 19th century. He came from an old and important family of Strumica. Famous relatives of him were the violinist Dimitrios Koukoudeas or Semsis and the teacher of Strumica's Girls' School, Aikaterini Koukoudea. 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. He was also enlisted in the Hellenic Navy as a leading seaman.
Macedonian Struggle
After his military service, he went to Macedonia and fought in the region of the Giannitsa Lake under the general command of Ioannis Demestichas. 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 and attacked the komitadji K. Delithanasis, in Bozej. The attack was successful, killing the komitadji and several of his men barricaded in the former's home. Eventually they left as an Ottoman military detachment appeared in the village. In March 1907, he was the leader of a small group involved in operations against komitadjis in Koufalia. He fought in the area of the Lake until the end of the Macedonian Struggle. Ioannis Demestichas wrote about Koukoudeas :
Balkan Wars
Before the Balkan Wars, during the Italo-Turkish War 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.
After the end of the Balkan Wars he fought for the Autonomous Republic of Northern Epirus. He then moved to the United States of America, where after the National Defence coup d'état in Thessaloniki and Greece's entry into World War I, he organized a militia to facilitate the transfer of volunteers to Greece. During the World War he fought as a reserve infantry officer, and was eventually commissioned into the Greek Army as a second lieutenant. He participated in the Greco-Turkish War, where he was captured by the Turks. After his liberation and the end of the war, he continued his career with the Greek Army, reaching the rank of colonel.
