Gürcü əfsanəvi tarixinə görə, Gürcüstan Tanrı Anasının həvari təsiridir.

Həvari Andrey xristianlığı təbliğ etməyə getdi . Birincisi, o, açıq sonra, İudeyadan şimala getdi, sonra şərqə yönəldi və o vaxt idi Egrisi (müasir Minqreliya) ərazisi olan Trabzon şəhərinə çatdı və İncil təbliğ etdikdən sonra o köçüb İberiyaya ölkəsinə köçdü.

Orada Həvari missionerliklə məşğul olaraq və guya hansısa möcüzələr göstərərək bir çox insanı xristianlığa çevirdi və onları vəftiz etdi.Vaxtanq V oğlu Vaxuştinin əhvalatına görə yerdə Həvari Andreyin Məryəm üçün ikona yerləşdirdiyi yerdən müalicəvi bulaq suyu axmağa başladı. Xristianlığı yeni qəbul etmiş şəxslərə kahinlər və keşiklər təyin edərək, Tanrı Anasının şərəfinə bir məbəd tikdirib və kilsə qaydasını qurduqdan sonra həvari onları tərk etdi.

Təxminən 100-cü ildə Roma yepiskopu Klement İmperator Trayan tərəfindən Tauridadakı qeyri-yaşayış yerlərinə sürgün edilir və burada guya hansısa möcüzələr göstərməklə və təlimatlarla Kolxidalıların xristianlığa sadiq qalmalarına nail olur. Onun Qara dəniz sahillərində sağlığında tikdirdiyi yetmiş kilsə arasında, eyni zamanda bir Kolxida kilsəsi də var idi.

318 və 337 illəri arasındakı dövrdə, çox güman ki, 324–326-cı illərdə Müqəddəs Ninanın missionerlik fəaliyyəti nəticəsində xristianlıq Gürcüstanda dövlət dini oldu. Kilsə təşkilatı Antakya Kilsəsinin daxilində idi.

Çar Vaxtanq I dövründə kilsə Antakyada bəzi muxtariyyət əldə edir və mərkəzi Mtsxetaya köçürülür.

609-cu ildə Gürcüstan Kilsəsi Xalkidon Şurasının qərarlarını qəbul etdi (506-cı ildə Dvin Şurasında gürcülər, ermənilərlə birlikdə Enotikonu qəbul etdilər) və bununla da özünü Erməni Həvari Kilsəsindən ayırdı .

GPK Sasanilər dövründə (VI–VII əsrlər) Fars atəşpərəstlərinə və Türk fəthləri dövründə (XVI–XVIII əsrlər) İslamla mübarizəyə tab gətirdi. Bu yorucu mübarizə Gürcüstan Pravoslavlığının tənəzzülə uğramasına və Müqəddəs Torpaqdakı kilsələrin və monastırların itirilməsinə səbəb oldu.

1744-cü ildə, Gürcü Kilsəsi Rusiyadakı Patriarx Nikon kimi oxşar islahatlar keçirdi.

1801-ci ildə Gürcüstan Rusiya İmperiyasının bir hissəsi oldu. Gürcü Kilsəsi Katolikosun tam sərəncamında olan və 18-ci əsrdə imperatorlar tərəfindən həyata keçirilən hökumət və maliyyə islahatları nəticəsində Rusiyada Kilsənin qanuni statusu ilə zidd olan nəhəng bir feodal iqtisadiyyatı idi. Baş general Aleksandr Tormasov tərəfindən hazırlanan və 1811-ci ildə I Aleksandra təqdim olunan layihəyə görə, Şərqi Gürcüstanda 13 yeparxiya əvəzinə iki yeparxiya quruldu: Mtsxeta-Kartala və Alaverdi-Kaxetiya. 21 iyun 1811-ci ildə Müqəddəs Sinod bu cür hərəkətlərə dair heç bir qanuni hüquq olmadan Katolikos-Patriarx II Antoniyanı vəzifəsindən uzaqlaşdırdı.

30 iyun 1811-ci ildən 1917-ci il marta qədər (de-fakto) Gürcüstan kilsəsi Rus Pravoslav kilsəsinin Gürcüstan Exarxiyası statusuna sahib idi. Patriarxlıq kilsə qaydalarına zidd olaraq ləğv edildi. Varlaam (Eristavi) 8 iyul 1811 (30 avqust 1814 – 14 may 1817) tarixində ilk Exarx oldu. 1817-ci ildən başlayaraq Gürcüstanın exarxları gürcü xalqına tamamilə yad olan, gürcü dilini bilməyən və gürcü kilsəsinin tam ruslaşdırılmasını təmin edən rus yepiskopları olurdular. Gürcü kilsəsinin avtokefal statusunun ləğvi ona gətirib çıxardı ki, kilsənin və monastırların bütün torpaq mülkiyyəti əlindən alındı, keşişlərin sayı azaldı, ruhanilərin sayının kəskin azalması ona gətirib çıxardı ki, nəticədə bir çox gürcü kilsələri bağlanmışdı. Kilsələrdə müntəzəm ibadət olmaması və "nəzarətsiz" qalmaları bir çox gürcü kilsələrinin Erməni Həvari Kilsəsinin əlinə keçməsi ilə nəticələndi. Ermənilər bəzən sadəcə kilsənin yerləşdiyi torpağı alır, ora öz keşişini gətirirdilər (zəngin Eçmiədzindən ruhanilərə pul ödəmək üçün kifayət idi) və kilsədə ibadəti bərpa edirdilər, lakin artıq "erməni" kilsəsində olduğu kimi. Bundan başqa, "yeni ələ keçirilən" kilsələrə münasibətdə erməni zəbtkarları standart işlənmiş sxem üzrə hərəkət edirdilər: köhnə yazıları məhv edir, ora erməni xaç daşları yerləşdirirdilər. Bir neçə ildən sonra kilsə erməni kilsəsinə çevrildi və onun ətrafında erməni yaşayış məntəqəsi yaranırdı.

1810-cu illərin sonunda Gürcüstan Exarxatlığına daxil olan Abxaz Katolikosluğu da ləğv edildi.

Varlaamdan (Eristavi) sonra qeyri-gürcü yepiskoplarından Exarxlar təyin olundu və bu da tez-tez yerli ruhanilərlə gərginliyə və münaqişəyə səbəb oldu, belə ki, Exarx Nikon (Sofiya) 28 may 1908-ci ildə Gürcüstan-İmereti sinodal ofisinin binasında öldürüldü. Exarxiya dövrü ən açıq şəkildə kanonik qaydaların pozulması, gürcü kilsəsinin kilsə mülklərinin oğurlanması, ən qədim kilsə incəsənət abidələrinin dağıdılması, kilsələrin ruslaşdırılması, gürcü ibadətinin və İlahiyyat məktəblərində gürcü dilinin qadağan olunması, dünyəvi hakimiyyət orqanları tərəfindən kahinlərə və iyerarxlara qarşı fiziki zorakılıq və hətta öldürülmələri ilə xarakterik idi.

1917-ci il martın 12-də (25 mart) Mtsxeta Şurasında Gürcüstan Kilsəsinin avtokefallığı elan edildi; Quriya-Mingrel yepiskopu Leonid (Okropiridze) Katolikos taxtının qəyyumu seçildi. 13 Martda Gürcüstanın Baş Exarxı və Kartala-Kaxetiya arxiyepiskopu Platona (Rozhdestvenski) kafedradan çıxarılması barədə xəbərdar edildi. Bu dəyişiklik Rus Pravoslav Kilsəsi tərəfindən tanınmadı.

27 mart 1917-ci ildə Müvəqqəti Hökumət Gürcü Kilsəsinin avtokefalisini prinsipcə tanıdı. 10 iyul 1917-ci ildə Müvəqqəti Hökumət və Sinodun ortaq iclasında Tiflis, Elizavetpol, Bakı, İrəvan, Kutaisi, Qara dəniz quberniyası və Qars, Batumi, Artvin, Zakatala və Suxumi dairələri rus kilsələrinin tərkibinə könüllü daxil olması üçün Qafqaz Exarxatlığının yaradılması qərara alındı. Feofilakt (Klementyev) Tiflisdə yepiskop təyin edildi və qısa müddət sonra Gürcü yepiskopları tərəfindən Gürcüstandan uzaqlaşdırıldı.

Moskva Patriarxı Tixon sentyabr 1917-ci Şurasının seçilmiş katolikos Kirion II (Sadzaglishvili) üçün 29 dekabr 1917 ildəki mesajında, gürcü kilsəsinin avtokefal bərpasını qınadı. Moskva Patriarxlığı ilə Gürcüstan Kilsəsi arasında əlaqə kəsildi.

1927-ci ildə Gürcü Kilsəsi Yeni Yulian təqviminə keçdi, lakin kilsə davamçılarının təzyiqi altında qərarını "təxirə salmalı" oldu.

19 noyabr 1943-cü ildə RPK Sinodunun qərarı ilə "Rus və Gürcü iki avtokefalçı Bacı Kilsəsi arasında dua və Evxaristik birlik" bərpa edildi. Eyni zamanda RPK Sinodu Kalkedon Şurasının 17. qaydasına istinad edərək " kilsə qaydalarına görə izah edərək bu qərarı verdi. Bu qaydaya əsasən Kilsə sərhədləri dövlət sərhədlərini izləməlidir.

1997-ci ildə Gürcüstan Kilsəsi Dünya Kilsələr Şurasından çıxdı .

GPK-nin 1995-ci il Nizamnaməsinə görə, kilsədə ən yüksək səlahiyyətli orqan Gürcüstan Kilsəsinin yerli şurası (Gürcü Kilsəsinin Müqəddəs Sinodu adlanır) və şuralararası dövrdə Gürcüstan Katolikos-Patriarxıdır. 23 dekabr 1977-ci ildən bəri bu vəzifədə İliya II oturur.

Hal-hazırda GPK-nin həm Gürcüstanda, həm də xaricdə 49 yeparxiyası var. 1992-ci ildən sonrakı Abxaziya yepiskopluğu faktiki olaraq Gürcüstan Kilsəsinə aid deyil. Katolikos İlia II-yə (2007) görə, "Rus Kilsəsinin nümayəndələrinin olduğu"Cənubi Osetiyada da kanonik bir tənzimləmə çatışmazlığı var.

2018-ci il tarixinə GPK üzvlərinin sayı 3 milyon nəfər olduğu təxmin edilir.