Sejarah paroki ini dituliskan dalam buku Ulang Tahun Paroki yang ke-7 dan ke-8 (Buku nomor 7 & 8). Yang menarik adalah bahwa paroki ini dimulai dari ketersediaan dan pengadaan lahan, agak berbeda dengan pembentukan paroki- paroki yang lain. Pengadaan lahan untuk gereja → lalu baru dikumpulkan umat gerejanya.

• Tahun 1996 : Ada informasi tentang upaya untuk pengadaan lahan untuk gereja dan puradi kalangan Angkatan Laut.
• Tahun 1998 : Ada info di kalangan Angkatan Laut tentang pengadaan lahan untuk kompleks gereja dan pura.
• Tahun 1999 : Setelah berkoordinasi dengan Paroki Salib Suci maka membentuk Panitia Pembangunan Gereja dan kemudian panitia ini berkoordinasi dengan Angkatan Laut. Dan semenjak itu di kalangan Angkatan Laut ini bukan lagi untuk pengadaan lahan untuk pura dan gereja tetapi menjadi pura dan gereja Katolik(maksudnya : awalnya adalah untuk gereja eukumene, ada pergeseran + penambahan “katolik”).
• Tahun 2001 : Proses pembangunan dimulai di lahan ini, tapi segera setelah itu dihentikan prosesnya karena ada isu penolakan pembangunan gereja di kalangan Angkatan Laut.
• Tahun 2002 : Proses pembangunan gereja dilanjutkan kembali setelah isu penolakan pembangunan gereja mulai mereda. Dan pada tahun ini dimulai proses perijinan IMB di Pemkab. Sidoarjo.
• Tahun 2005 : Gedung gereja sudah jadi dan diresmikan, disusul dengan pembangunan pastoran. Setelah pastoran jadi, lalu dibentuklah Stasi Santo Paulus. Awalnya yang melakukan proses-proses tersebut adalah Paroki Salib Suci, tetapi ketika membentuk Stasi Santo Paulus dirasa bahwa area dari stasi baru dari Paroki Salib Suci ini terlalu sedikit umatnya, maka Romo Heri (Paroki Salib Suci – Tropodo) meminta pada paroki sekitar (yaitu Paroki Sidoarjo, Pagesangan dan Gembala yang Baik) untuk menyumbangkan masing-masing 1 (satu) wilayah untuk digabung menjadi satu Stasi Santo Paulus.
• Tanggal 1 Mei Tahun 2008 : Stasi Santo Paulus ini menjadi paroki, dan ditetapkan tanggal 1 Mei sebagai hari jadi Paroki St. Paulus – Juanda.
• Tahun 2013 : Dimulai pembangunan Balai Paroki
• Tahun 2014 : Pergantian romo kepala paroki dari Romo Sony ke Romo Tri Kuncoro Yekti (Romo Cun).

Sejak Agustus 2014 Romo Cun masuk ke Paroki Santo Paulus, kesan awal :

• paroki ini sedang dalam dinamika untuk menjadi paroki →Paroki ini belum matang, masih dalam proses untuk menjadi paroki.

Sehingga ada 3 (tiga) hal yang perlu mendapat perhatian (pada awal-awal dinamika di tahun 2014 ini) sebagai berikut :

1. Harus diusahakan integrasi warga sebagai komunitas hidup Dari proses penggabungan dari beberapa paroki, teramati bahwa pengenalan lintas wilayah adalah masih kurang. Langkah awal :
   • Mendorong terjadinya integrasi
   • Membangun sense of belonging (rasa memiliki) sebagai warga
2. Melanjutkan pembangunan Balai Paroki
3. Menata organisasi pastoral di paroki (DPP, BGKP, pengelolaan keuangan, pengelolaan pastoran, karyawan (SDM),)