Pada tahun 1975, TLDM memerlukan sebuah pasukan khusus untuk menguatkuasakan perairan Malaysia dari diceroboh oleh sebarang keganasan di laut, misalnya lanun. Pasukan ini dikehendaki untuk menjalani latihan peperangan moden dilaut. Atas keperluan inilah, TLDM telah menghantar 30 orang pegawai dan anggota di Pusat Latihan Peperangan Khas, Kem Sungai Udang, Melaka dan seterusnya dihantar ke Surabaya, Indonesia untuk mendapat latihan khas dari pasukan elit KOPASKA (Komando Pasukan Katak) Tentera Nasional Indonesia - Angkatan Laut dan bermulanya detik penubuhan pasukan elit TLDM ini. Walaubagaimanapun, salah seorang daripada 69 anggota pelatih TLDM yang menjalani latihan asas komando di Surabaya gagal menamatkan latihan setelah terpaksa dihantar ke hospital akibat kecederaan patah kaki. Selepas menjalani latihan dari KOPASKA, pasukan ini kemudiannya dihantar berkursus ke Portsmouth, United Kingdom di bawah sel latihan oleh Royal Marine Commando British dan Coronado, Amerika Syarikat oleh US Navy SEALs.[1][3][4]

Bersama dengan anggota-anggota US Navy SEALs yang menerima latihan asas komando, anggota PASKAL yang dilatih oleh SEALs ini mengikuti latihan asas komando di seluruh formasi latihan asas tentera laut Amerika, khasnya di Coronado, California dan Norfolk, Virginia terutamanya latihan yang melibatkan operasi dibawah permukaan air, amfibia, sabotaj serta latihan-latihan lain yang cukup mencabar yang tidak dapat dilakukan oleh pasukan tentera yang biasa. Antara pegawai PASKAL yang turut mendapat latihan daripada pasukan elit Amerika ini ialah Leftenan Ahmad Ramli bin Kardi. Setelah menamatkan latihan daripada ketiga-tiga pasukan elit ini, PASKAL memulakan pengoperasiannya di Malaysia pada tahun 1 Oktober, 1980 mempertahankan Zon Ekonomi Eksklusif (EEZ) sejauh 200 batu nautika dari perairan Malaysia.[5]