Keberhasilan PSMS ini membuat PSMS Medan ditunjuk PSSI mewakili Indonesia di Piala Emas Aga Khan 1967 yang berlangsung di Bangladesh. Dan akhirnya di Turnamen ini PSMS berhasil menjadi Juara setelah di Final mengalahkan tim tuan rumah Mohammaden 2-0. Ini adalah gelar Internasional pertama yang sukses diraih oleh PSMS. Keberhasilan ini membuat seluruh skuad PSMS mendapat anugerah “Warga Utama” dari Walikota Medan Sjoerkani.

Seusai menjadi Juara Piala Raja 1968 di Bangkok para pemain timnas dikontrak secara profesional oleh TD Pardede di klubnya, Pardedetex. Pemain yang dikontrak antara lain Soetjipto Soentoro, Sinyo Aliandoe, Iswadi Idris, Judo Hadianto , Muliyadi (Persija), M. Basri (PSM), Abdul Kadir , Jacob Sihasale (Persebaya), Anwar Ujang (Persika), Max Timisela (Persib . Namun saat itu Pardedetex meski mengontrak pemain secara profesional namun dalam kompetisi bernaung di kompetisi Kelas Utama/Divisi Utama PSMS sehingga secara otomatis skuad Pardedetex memperkuat PSMS di Kejurnas/Divisi Utama PSSI 1969.

Kehadiran para pemain Timnas ini membuat Zulkarnaen Pasaribu tidak terpilih memperkuat PSMS saat itu. Walau sempat kecewa karena permainannya yang tengah bagus – bagusnya saat itu dirinya tidak patah arang. Zulkarnaen Pasaribu terus mengasah kemampuannya di Bintang Utara.

Seusai memperkuat PSMS di AFC Champions Cup 1970 di Teheran Soetjipto Soentoro,Sinyo Aliandoe,Iswadi Idris, Judo Hadianto, Muliyadi, M.Basri Abdul Kadir, Jacob Sihasale dan Max Timisela kembali ke klub asal mereka sebelum bergabung dengan PSMS. Hanya Anwar Ujang yang tetap bertahan di Medan dan menjadi rekan setim Zulkarnaen Pasaribu di Bintang Utara.

PSMS yang saat itu dilatih oleh Zulkarnaen Nasution mulai bersiap menghadapi Kejurnas PSSI 1971.Pada 14 Juni 1971 PSV Eindhoeven yang saat itu diperkuat Guus Hiddink berkunjung ke Medan dan menghadapi PSMS. Zulkarnaen Pasaribu turut memperkuat PSMS saat itu bersama Ronny Pasla, Sukiman, Yuswardi, Anwar Ujang, Tumsila, Wibisono, Tumpak Uli Sihite, Sarman Panggabean, Saleh Harahap, Suwarno, Sunarto, Nobon dan lain-lain.

Walau sempat memberi perlawanan ketat akhirnya skuad PSMS harus takluk 0-4 dari PSV Eindhoeven lewat gol yang dicetak Gerrit Van Tilburg, Willy Van Der Kuijlen, Johan Devrindt, dan Guus Hiddink. Walaupun kalah dari PSV namun makin menguatkan semangat para pemain PSMS bahwa mereka bisa bersaing di Kejurnas PSSI 1971.

Dan akhirnya pada Kejurnas PSSI 1971 PSMS kembali sukses menjadi Juara. Gelar ini membuat PSMS mempertahankan gelar yang mereka raih pada 1967 dan 1969 sekaligus menjadikan PSMS sebagai klub Indonesia pertama sesudah Indonesia merdeka yang sukses menjadi Juara Kejurnas PSSI 3 kali berturut – turut.

Kiprah sukses Zulkarnaen Pasaribu terus berlanjut dengan kesuksesannya membawa PSMS menjadi Juara Soeharto Cup 1972, Marah Halim Cup 1972 dan 1973 serta Jusuf Cup 1974.

Pada 5 - 13 Maret 1974 berlangsung Kejuaraan Antar Wilayah PSSI 1974. Zulkarnaen Pasaribu bersama rekan – rekannya di PSMS saat itu memperkuat PSSI Wilayah I.PSSI Wilayah I yang bermaterikan 90% skuad PSMS tampil di Final menghadapi PSSI Wilayah III yang bermaterikan skuad Persebaya.

PSSI Wilayah I tampil sebagai Juara setelah menaklukkan PSSI Wilayah III dengan skor 3-2. Zulkarnaen Pasaribu sendiri mencetak satu gol dalam kemenangan PSSI Wilayah I tersebut.

Kesuksesan ini membuat PSSI Wilayah I ditunjuk mewakili Indonesia ke Piala Presiden IV/1974 di Seoul, Korea Selatan. Prestasi PSSI Wilayah I cukup membanggakan dengan meraih gelar Runner Up setelah dikandaskan tuan rumah Korea Selatan di babak final.Prestasi ini membuat nama PSMS makin harum di pentas Nasional dan Internasional.