塞浦路斯教会（希腊语：Ἐκκλησία τῆς Κύπρου）是以塞浦路斯岛为范围的自主希腊正教会，于431年的以弗所大公会议后，从安提阿教会独立而成为最早的自主正教会之一。
根据圣经宗徒大事录的记载，在保禄宗徒第一次出外传教的旅途的第一站就是塞浦路斯岛。与他同行的还有巴尔纳伯和马尔谷。后来巴尔纳伯也被视为第一位塞浦路斯主教，并死于当地。
四世纪时，罗马皇帝君士坦提乌斯二世出资重建受地震摧残的岛上城市萨拉米斯，并且将之重新命名为君士坦提亚，并在此地建立主教座。其中担任主教者包含教父圣厄丕法尼（Epiphanius of Salamis）
塞浦路斯教会的自主权则源自于431年的以弗所大公会议，当时安提阿主教试图取消塞浦路斯教会因习惯而来的自主权，于是当时的萨拉米斯总主教拉吉努斯（Rheginus）将之提交由大会讨论。最后会议决议此特权不该撤销，并将之列在第八条决议。自此塞浦路斯教会就由萨拉米斯总主教管理。
478年，据传当时的萨拉米斯总主教安提蒙斯（Anthemios）因为神视而找到了巴尔纳伯的圣髑，因此获得了拜占庭皇帝芝诺的支持，因此巩固了塞浦路斯教会的自主权。
七世纪末，拜占庭皇帝查士丁尼二世为了因应阿拉伯军队对塞浦路斯岛的侵扰，因此将岛上人口迁移到今日的埃尔代克所在地，并将新建立的都市命名为新查士丁尼亚（希腊语：Νέα Ιουστινιανή,）。萨拉米斯总主教也将教座迁至当地，自此“新查士丁尼亚及全塞浦路斯总主教”就成为塞浦路斯教会领导者的头衔至今。
1091年，十字军占领了塞浦路斯岛，建立了塞浦路斯王国。并且开始任命自己的天主教主教，正教会的主教不是迁移就是失去教座。
1571年奥斯曼帝国占领了塞浦路斯岛，正教会恢复了一定的地位。然而因为奥斯曼帝国实行米利特制度的关系。塞浦路斯教会被交由君士坦丁堡普世牧首管理。总主教也恢复了影响力。
1821年，在希腊独立战争中，塞浦路斯岛上也掀起了反对奥斯曼统治的活动，当时的总主教齐布理亚诺斯（Kyprianos）因为身为塞浦路斯民族主义者精神领袖的身份，与其他教会高阶神职人员一起遭到奥斯曼政权处刑，这一事件导致了塞浦路斯岛上的希腊合并主义。
1878年，奥斯曼帝国为了获得英国抵御俄罗斯的协助，将塞浦路斯的管辖权做为回报。自此塞浦路斯成为英国管辖区。1923年，土耳其共和国签属了洛桑条约，以塞浦路斯等前奥斯曼领地为代价换取了国际承认。随后在1925年塞浦路斯成为了英国的殖民地。
然而岛上的希腊合并主义者却不愿意接受由英国管辖的结果，因此在1931年开始爆发多起武装行动。这起事件导致英国对塞浦路斯的高压管控，而作为民族主义的主导人，塞浦路斯教会两位主教遭到了英国政权流放。并导致自时任总主教基里洛斯三世在1933年过世后，直到1947年为止的空缺期。被流放的二位主教中的凯里尼亚主教马卡里奥斯在解除流放返国后，于1948年被推举为新任的总主教，是为马卡里奥斯二世。
二战结束后，受到民族自决风气的影响，塞浦路斯的定位被联合国督请英国、希腊和土耳其商议。结果在1955年8月的会议中，因为英国的反对而使得塞浦路斯无法脱离英国。因此引发希腊裔的塞浦路斯民族主义者发起武装，攻击英国政府机关，这导致在1956年总主教马卡里奥斯三世被视为武装集团领袖而遭到英国囚禁，直到他于1957年3月发表反对武装行动的宣言才获释。最后在英国、希腊和土耳其三国的外交协调下，于1958年签署了苏黎世－伦敦协议，在不接受岛上与希腊统一主义的前提下给予塞浦路斯岛独立的地位。马卡里奥斯三世总主教也被选为首任总统。
