Patoulidis, wiens grootouders afkomstig zijn van Thessaloniki, groeide op in Brussel.[1] In 2013 wekte hij als twaalfjarige jeugdspeler van RSC Anderlecht de interesse op van FC Barcelona, en twee jaar later toonde ook Manchester City interesse, maar uiteindelijk was het Standard Luik dat de net geen zestienjarige Evangelos samen met zijn één jaar oudere broer Constantinos in 2017 binnenhaalde.[2][3][4]
Patoulidis slaagde er echter niet in om door te stromen naar het eerste elftal van Standard, en in de zomer van 2020 werd zijn aflopende contract er niet verlengd. De middenvelder bleef een poos zonder club. Na een proefperiode bij Lommel SK werd hij niet weerhouden, maar na een overtuigende prestatie in een oefenwedstrijd tegen KSKV Zwevezele kreeg hij in oktober 2020 een contract voor drie seizoenen bij KV Oostende.[5][6] Op 29 november 2020 maakte hij zijn profdebuut: in de competitiewedstrijd tegen KV Kortrijk kreeg hij meteen een basisplaats van trainer Alexander Blessin.[7] Later dat seizoen kreeg hij nog drie invalbeurten van telkens een handvol minuten.
In het seizoen 2022/23 wordt Patoulidis verhuurd aan FC Den Bosch.[8] Daar maakte hij op 2 september 2022 zijn debuut in de met 1-2 verloren thuiswedstrijd tegen PEC Zwolle. In de 70e minuut verving hij Sebastiaan van Bakel.[9] Op 12 september 2022 maakte de Belg zijn eerste doelpunt in het betaald voetbal: in de 47e minuut scoorde hij de 1-1 in de met 3-1 verloren uitwedstrijd bij Jong PSV.[10]