Two months later, Nikolaos regretted his decision and escaped. He found his father, who secretly helped him flee to the village of Keramidi. From there, along with some craftsmen, he travelled to Crete. The craftsmen mistreated him, and he left them. After wandering around in a forest, the young Nicholas met a priest living near a small chapel. The priest had recently lost his only son and adopted Nicholas. When the priest died three years later, Nicholas left for Mt Athos. Eventually he reached the Karakallos Monastery, where he confessed, repented, and became a monk two months later, taking the name Gedeon.
He became a trusted and respected member of the faith, and in 1797 was appointed, along with the elderly Abbot Gabriel, to a dependency of the Transfiguration (Metamorphosis) Monastery, in the area of Rethymno, Crete. He returned to the Karakallos Monastery six years later, where he continued his practice. He was constantly remorseful about the denial of his faith.