STAFUKA dibangun di atas harapan akan terciptanya suasana rukun antar-agama (khususnya Islam-Kristen).  Sejarahnya bermula dengan kunjungan mahasiswa Angkatan V  (1998-1999) Sekolah Tinggi Teologi (STT) Apostolos Jakarta ke Himpunan Mahasiswa Islam (HMI) Komisariat Fakultas Ushuluddin IAIN Sunan Kalijaga Yogyakarta pada tanggal 6-9 Desember 1999. Dalam kunjungan tersebut disepakati akan dibentuknya suatu forum kerja sama antara kedua institusi,  yang nantinya akan dibahas lebih lanjut di Jakarta.
          

Pada  tanggal 15-17 April 2000,  puluhan mahasiswa yang mengatasnamakan Fakultas Ushuluddin IAIN Sunan Kalijaga Yogyakarta  berkunjung  ke  STT  Apostolos sebagai bentuk kunjungan balik, sekaligus dalam rangka menindaklanjuti kerja sama yang telah terjalin pada bulan Desember 1999. Akhirnya, pada tanggal 19 April 2000, ditandatanganilah Memorandum of Understanding  antara Dr. K.A.M. Jusuf Roni selaku Ketua STT Apostolos Jakarta  dengan Dr.  Djam'anuri selaku Dekan Fakultas Ushuluddin IAIN Sunan Kalijaga Yogyakarta. Peristiwa paling bersejarah bagi  STAFUKA ini berlangsung di GKRI Alfa Indah, sebagai tanda resminya kerja sama antara kedua institusi.
          

Siangnya, beberapa mahasiswa segera melakukan pertemuan di ruang Elia,  STT Apostolos Jakarta,  untuk menyusun format kerja sama yang lebih real. Pertemuan itu dipimpin oleh Costa Rantelinggi (Ketua Senat Mahasiswa STT Apostolos Jakarta) dan Eko Cahyono (Ketua HMI Komfak Ushuluddin IAIN Sunan Kalijaga Yogyakarta).
Pertemuan tersebut menyepakati dibentuknya  Forum Komunikasi STT Apostolos Jakarta-Fakultas Ushuluddin IAIN Sunan Kalijaga Yogyakarta, dan langsung membentuk Presidium beserta divisi-divisi yang diperlukan. Nama STAFUKA sendiri merupakan singkatan dari nama forum tersebut. Nama ini tidak muncul bersamaan dengan lahirnya forum tersebut, melainkan baru diberikan menjelang diadakannya kegiatan Pekan Komunikasi Agama-agama I (PEKA 1). Nama ini diberikan oleh  Yosi  Rorimpandei  dan  Abdurrahman  Effendi ketika sedang dalam persiapan pelaksanaan PEKA 1 tersebut.
          

Pada akhir Juli 2000, jaringan kerja sama STAFUKA diperluas dengan menambah relasi baru,  yaitu  Institut Studi Islam Darussalam (ISID) Gontor dan Institut Agama Islam Tribakti (IAIT) Kediri. Dalam kunjungan ke  Gontor dan Kediri itulah kemudian dirancangkan suatu bentuk  sosialisasi  forum  dan  dialog bentuk baru  antara  Islam-Kristen. Atas prakarsa Glorius Bawengan, M.Th selaku salah satu Pembina STAFUKA, disepakatilah untuk diadakan Pekan Komunikasi Agama-agama (PEKA). Kegiatan ini beberapa kali mengalami penundaan akibat berbagai masalah yang dihadapi, di antaranya masalah jarak antara keempat institusi (STT Apostolos, IAIN Sunan Kalijaga, ISID Gontor, dan IAIT Lirboyo).
          

Untuk itu, STT Apostolos mencoba mencarikan solusi terbaik dengan cara menjalin relasi dengan IAIN Syarif Hidayatullah Jakarta. Atas kerja sama yang baik, pada tanggal 1 dan 2 Juni 2001 digelarlah PEKA  untuk  pertama kalinya di Aula Serba Guna dan Aula Madya IAIN Syarif Hidayatullah Jakarta. Usai kegiatan PEKA tersebut, diadakan evaluasi kegiatan sekaligus diterimanya IAIN Syarif Hidayatullah Jakarta sebagai anggota  STAFUKA  yang baru. Dalam evaluasi itu juga disepakati akan diadakannya PEKA 2 di Yogyakarta, yang akhirnya bisa terselenggara dengan baik pada tanggal 9-13 November 2001 di Aula IAIN Sunan Kalijaga Yogyakarta.