Instituutin ensimmäinen arkeologinen kaivauskohde, Arethousan Paliambelan varhaiskristillinen kirkko sijaitsee Pohjois-Kreikassa, noin 100 kilometriä Thessalonikista itään ja noin 20 kilometriä muinaisesta Amfipoliksesta länteen. Kirkko löydettiin metsätien rakentamisen yhteydessä vuonna 1994, ja sitä tutkittiin vuosina 1994–1995 paikallisen Eforiaatin toimesta. Suomen Ateenan-instituutti jatkoi kaivauksia  vuosina 1999–2002. Kaivauksia seurasi lattiamosaiikkien konservointi ja seinämuurien restaurointi vuosina 2003–2004. Projektin johtajana toimii Arja Karivieri.

Kolmilaivaisesta basilikatyyppisestä kirkosta on paljastettu merkittävät opus sectile– ja opus tessellatum -tekniikoilla tehdyt geometris- ja eläinaiheiset lattiamosaiikit. Lisäksi vuonna 2002 löydettiin baptisterio ja pohjoislaivasta viinintuotantoon ja ruuan varastointiin käytetty huone. Kirkon rakentaminen ajoittuu 400-luvun lopulle tai 500-luvun alkuun. Tästä kertoo mosaiikkien lisäksi runsas löytömateriaali: merkittävä osa keramiikasta, öljylamppujen jäänteistä, marmorifragmenteista ja yli 150 kolikosta ajoittuu myöhäisroomalaiselle ja varhaisbysanttilaiselle kaudelle. Lisäksi kirkon ympäristöstä löydetyt, klassiselta tai hellenistiseltä periodilta varhaisbysanttilaiselle kaudelle ajoittuvat hauta- ja asuinjäänteet sekä tuontikeramiikka kertovat alueen laajemmasta asutushistoriasta ja merkityksestä Thessalonikista Konstantinopoliin kulkeneen Via Egnatia -tien läheisyydessä.

Kirkko tuhoutui ja sen kattorakenteet sortuivat 500-luvun lopussa tai 600-luvun alkupuolella. Syynä tuhoon pidetään joko slaaveja, joiden tiedetään  tuhonneen useita kaupunkeja Kreikassa 580-luvulla, tai  maanjäristystä – kirjalliset lähteet kertovat useista maanjäristyksistä myöhäisroomalaisella ja varhaisbysanttilaisella kaudella.