นิโคโลดิสเริ่มเล่นกีฬาตั้งแต่อายุยังน้อย โดยเข้าร่วมสโมสรอิราคลิสตามธรรมเนียมในสมัยนั้น นักกีฬาเยาวชนจะเล่นกีฬามากกว่าหนึ่งชนิดในสโมสร จนกว่าจะเลือกได้ว่าจะมุ่งเน้นกีฬาชนิดใด ดังนั้น นอกเหนือจากฟุตบอลแล้ว นิโคโลดิสยังเล่นบาสเกตบอลด้วย โดยเคยเล่นให้กับทีมเยาวชนของอิราคลิสความสามารถด้านฟุตบอลทำให้เขาหันมามุ่งเน้นกีฬาชนิดนี้ และหลังจากที่เขาได้เข้าร่วมทีมระดับต่างๆ ของสโมสรแล้ว เขาก็ได้รับการเลื่อนชั้นขึ้นสู่ทีมชุดใหญ่ของอิราคลิสในปี 1969

ในตำแหน่งกองกลางตัวรับ เขาสร้างความประทับใจด้วยเกมการเล่นที่ชาญฉลาดแม้จะมีอายุยังน้อย เขาเล่นให้กับอิราคลิสเป็นเวลาแปดฤดูกาลติดต่อกัน และเป็นหนึ่งในผู้เล่นที่ดีที่สุดของทีม อย่างไรก็ตาม อาชีพการค้าแข้งของเขากับอิราคลิสต้องมัวหมองเมื่อชื่อของเขาเข้าไปพัวพันกับคดีติดสินบน เมื่อวันที่ 28 พฤษภาคม 1975 ก่อนการแข่งขันรอบรองชนะเลิศของฟุตบอลถ้วยระหว่างอิราคลิสและ พา นาธิไนกอสที่สนามคาฟตันโซกลิโออดีตผู้เล่นของพานาธิไนกอสและอิราคลิสอย่าง จอร์จอส โรคิดิส ได้รับคำสั่งจากอันโตนิส มันต์ซาเวลากิส เอเยนต์ของพานาธิไนกอส ให้ไปที่โรงแรมกับทีมอิราคลิส และเสนอเงินให้กับนิโคโลดิสและชาลิอัมปาเลียสเพื่อให้ลดฟอร์มการเล่นในเกมนั้น ในระหว่างนั้น โรคิดิสถือช่อดอกไม้ ทำให้คดีนี้ถูกเรียกว่า "คดีดอกไม้" ฝ่ายบริหารของอิราคลิสตัดชื่อผู้เล่นทั้งสองคนออกจากทีมในนัดนั้นเนื่องจาก "ความผิดทางวินัย" กระบวนการทางกฎหมายได้ดำเนินตามมา โดยมีการบันทึกความผิดของทุกคน และในการประชุมและการลงคะแนนของคณะกรรมการพิเศษของHFFพานาธิไนกอสได้รับการยกฟ้องเนื่องจากมีข้อสงสัยจากการลงคะแนนของจอร์จอส อันเดรียโนปูลอสในขณะที่โรคิดิสและชาลิอัมปาเลียสถูกแบนตลอดชีวิต สำหรับนิโคโลดิสได้รับการผ่อนปรนและยกฟ้องโดยมีปัจจัยบรรเทาโทษคืออายุยังน้อย^{[ 1 ]}กรณีนี้ทำให้ความสัมพันธ์ระหว่างนิโคโลดิสและฝ่ายบริหารของสโมสรแตกหัก โดยนักเตะหมดความโปรดปรานและไม่ได้ลงเล่นในรอบชิงชนะเลิศฟุตบอลถ้วยเมื่อพวกเขาคว้าแชมป์ได้จากการเอาชนะโอลิมปิอาโกส^{[ 2 ]}

เมื่อวันที่ 31 กรกฎาคม พ.ศ. 2519 เขาถูกย้ายไปอยู่กับAEK Athensด้วยค่าตัว 3.5 ล้านดรัคมา [ ^{3 ] นิ}โคโลดิสปรับตัวเข้ากับทีมได้ทันที และภายใต้ผู้จัดการทีมฟรานติเช็ก ฟาดร์ฮอนช์เขากลายเป็นผู้เล่นสำคัญในแดนกลางของทีม เมื่อวันที่ 15 กันยายน พ.ศ. 2519 นิโคโลดิสทำประตูแรกของเขา โดยแนะนำลูกฟรีคิก "สายฟ้า" ของเขาให้แฟนๆ AEK รู้จัก และทำประตูขึ้นนำใน เกม ยูฟ่าคัพกับไดนาโม มอสโกในบ้าน ซึ่งจบลงด้วยชัยชนะ 2-0 ^{[ 4 ]}ในรอบต่อไปของทัวร์นาเมนต์เดียวกัน เขายังทำประตูจากลูกฟรีคิกอีกครั้ง คราวนี้กับดาร์บี้ เคาน์ตี้ทำประตูตีเสมอในเกมเยือนสุดมันส์ที่ชนะ 3-2 ^{[ 5 ]}เมื่อวันที่ 25 มีนาคม พ.ศ. 2522 เขาทำสองประตูในเกมเยือนที่ชนะปานาไชกิ^{[ 6 ]}เมื่อวันที่ 8 เมษายน พ.ศ. 2522 นิโคโลดิสยิงประตูชัยด้วยลูกยิงทรงพลังในเขตโทษเอาชนะพานาธิไนกอส และสามนาทีต่อมาเขาก็ถูกไล่ออกพร้อมกับลิวาธินอสหลังจากมีการทะเลาะวิวาทกันอย่างรุนแรงระหว่างผู้เล่น^{[ 7 ]}ในช่วงที่เขาเล่นให้กับสโมสร เขาคว้าแชมป์สองรายการในประเทศในฤดูกาล พ.ศ. 2521 และแชมป์ลีกในปี พ.ศ. 2522 ขณะเดียวกันเขาก็เป็นสมาชิกคนสำคัญของทีมที่เข้าถึงรอบรองชนะเลิศของยูฟ่าคัพในปี พ.ศ. 2520 ^{[ 8 ]}

ฤดูร้อนปี 1979 ลูคัส บาร์ลอสเจ้าของสโมสร AEK ตกอยู่ในสถานการณ์ทางการเงินที่ยากลำบาก พยายามรักษาผู้เล่นฝีมือดีของสโมสรไว้ คืนหนึ่ง บาร์ลอสได้พบกับสตาฟรอส ไดฟาส ประธานสโมสรโอลิมปิอาโกสโดยบังเอิญ บาร์ลอสเล่าถึงปัญหาทางการเงินของเขาให้ไดฟาสฟัง^{[ 9 ]}ซึ่งในที่สุดก็ทำให้มีการย้ายทีมของนิโคโลดิสมาอยู่กับทีมสีแดงขาวในเดือนธันวาคม 1979 ด้วยค่าตัว 6.5 ล้านดรัคมา^{[ 10 ] [ 11 ]}

เมื่อวันที่ 11 พฤษภาคม พ.ศ. 2523 ประตูที่เขายิงใส่พานาธิไนกอสที่สนามคาราอิสคาคิสทำให้โอลิมปิอาโกสชนะด้วยสกอร์ 1-0 ส่งผลให้โอลิมปิอาโกสได้แชมป์ระดับอาชีพเป็นครั้งแรก^{[ 12 ]}ส่งผลให้โอลิมปิอาโกสได้ไปเล่นรอบเพลย์ออฟชิงแชมป์ ในการแข่งขันที่เมืองโวลอสทีมสีแดงและขาวเอาชนะอาริส ไปได้ 2-0 และคว้าแชมป์ระดับอาชีพเป็นครั้งแรกเช่นกัน^{[ 13 ]}กับโอลิมปิอาโกส เขาคว้าแชมป์ติดต่อกัน 3 สมัย และแชมป์ถ้วยอีก 1 สมัย รวมถึงการคว้าแชมป์สองรายการในประเทศในปี พ.ศ. 2524

ในช่วงฤดูร้อนปี 1982 การกลับมาของZlatko Čajkovskiสู่ม้านั่งสำรองของ AEK Athens เกิดขึ้นพร้อมกับการกลับมาของ Nikoloudis สู่สโมสร การกลับมาของเขาเป็นทางการในวันที่ 25 กรกฎาคม เมื่อเขาถูกซื้อตัวมาจาก Olympiacos พร้อมกับเพื่อนร่วมทีมChristos Arvanitisด้วยค่าตัวรวม 12 ล้านดรัคมา^{[ 14 ]}อย่างไรก็ตาม เขาเป็นเพียงเงาของตัวเองในอดีตเมื่อครั้งเล่นให้กับสโมสรครั้งแรก ในเดือนมิถุนายน 1983 ก่อนสิ้นสุดฤดูกาล เขาเดินทางไปแคนาดาเพื่อเล่นให้กับInter-MontréalในCanadian Professional Soccer League ปี 1983แต่สโมสรก็ยุบตัวลงกลางฤดูกาลเนื่องจากขาดทุนอย่างหนัก^{[ 15 ]}เมื่อเขากลับมากรีซหนึ่งเดือนต่อมาและ AEK คว้าแชมป์Greek Cupบทบาทของเขาในทีมก็ลดลง

ในที่สุดเขาก็ถูกย้ายไปอยู่กับอพอลลอน คาลามาริอัสเมื่อวันที่ 9 ธันวาคม พ.ศ. 2526 ด้วยค่าตัว 1 ล้านดรัคมา^{[ 16 ]}ในอพอลลอน เขาเล่นอยู่หนึ่งฤดูกาลเคียงข้างกับกริกอริส พี่ชายของเขา และทั้งสองคนก็มีส่วนช่วยให้ทีมอยู่ในดิวิชั่นหนึ่งได้ หลังจากนั้น นิโคโลดิสก็ไปแข่งขันกับเลวาเดียโกสในดิวิชั่นสองจนถึงฤดูร้อนปี พ.ศ. 2529 เมื่อเขาเลิกเล่นฟุตบอล^{[ 17 ]}