Wilayah Paroki Pluit awalnya merupakan wilayah Stasi Jembatan Tiga dalam Paroki Toasebio. Saat itu stasi ini telah memiliki sebuah bangunan gereja yang bernama Gereja Sang Penebus. Stasi Jembatan Tiga dibentuk pada tanggal 11 Februari 1964. Setahun kemudian, yakni pada 17 Januari 1965, status stasi ditingkatkan menjadi Paroki Jembatan Tiga, Gereja Sang Penebus, oleh Uskup Agung Jakarta, Adrianus Djajasepoetra, S.J.[1]
Karena adanya rencana perluasan pembangunan Jalan Jembatan Tiga, Gereja Sang Penebus dipindahkan ke Pluit pada tahun 1976. Saat itu nama gereja diubah menjadi Gereja Stella Maris. Gereja ini kemudian diresmikan oleh Leo Soekoto, S.J. pada tahun 1977.[2]
Pada tahun 1993, sebagian wilayah paroki ini dimekarkan menjadi Paroki Kapuk (Gereja Santo Philipus Rasul), disusul dengan pemekaran Paroki Pantai Indah Kapuk (Gereja Regina Caeli).
Gereja Stella Maris mengalami renovasi kembali dan diresmikan pada 18 November 2012 oleh Ignatius Suharyo, Uskup Agung Jakarta.
Bangunan
Renovasi gereja pada tahun 2012 dilaksanakan dengan arsitek Budiman Hendropurnomo.[3] Bagian depan gereja memiliki bentuk yang menyerupai bentuk oval bersusun tiga (concentric oval). Dinding bangunan gereja pada sisi luar berlapis dengan berbatuan. Menara gereja terbuat dari pipa besi. Pada bagian luar gereja juga terdapat Gua Maria yang disebut sebagai Plasa Maria. Patung Bunda Maria terbuat dari batu alam.
Bangunan dalam gereja memiliki kapasitas 1.400 hingga 1.500 umat. Pada dinding dalam dilapisi dengan kayu balok jati. Lantai gereja terbuat dari keramik yang menyerupai batu alam. Terdapat tiga buah balkon gereja yang memiliki bentuk seperti buritan kapal dengan haluan sendok (spoon bow). Pada pintu keluar utama gedung gereja terdapat tulisan Sit Deus In Itinere Tuo yang berarti "Tuhan menyertai perjalananmu".
Gereja Stella Maris menjadi salah satu finalis dalam World Architecture Festival 2015.[4]