Kabupaten Cilacap terdiri atas 24 kecamatan, yang terbagi lagi menjadi sejumlah desa dan kelurahan. Desa-desa tersebar di 21 kecamatan, sedangkan kelurahan ada di 3 kecamatan eks kota administratip Cilacap. Kecamatan-kecamatan tersebut adalah Dayeuhluhur, Wanareja, Majenang, Cimanggu, Karangpucung, Sidareja, Gandrungmangu, Kedungreja, Patimuan, Cipari, Bantarsari, Kawunganten, Jeruklegi, Kesugihan, Maos, Sampang, Kroya, Adipala, Binangun, Nusawungu, Kampung Laut, Cilacap Utara, Cilacap Tengah dan Cilacap Selatan.

Menurut cerita rakyat penduduk asli Kampung Laut merupakan anak keturunan dari para prajurit Mataram yang datang ke daerah Kampung Laut untuk mengamankan daerah perairan Segara Anakan dari gangguan bajak laut orang Portugis. Para prajurit itu dipimpin oleh empat orang wiratamtama, yaitu yang bernama Jaga Playa, Jaga Praya, Jaga Resmi dan Jaga Laut.

Setelah keadaan aman, para wiratamtama dan anak buahnya tersebut tidak mau kembali ke pusat kerajaan Mataram, mereka tetap tinggal di kawasan Cilacap dan sekitarnya misalnya Jaga Playa dan Jaga Praya kemudian bermukim di daerah yang sekarang disebut Klapalima, sementara itu Jaga Resmi dan Jaga Laut memilih tinggal di Pulau Nusakambangan. Jaga Resmi bermukim di daerah yang kini disebut Legok Pari, sedangkan Jaga Laut bertempat tinggal di Gebang Kuning atau yang sekarang lebih dikenal dengan nama Kembang Kuning.

Ketika kekuasaan Kerajaan Mataram makin melemah dan akhirnya dikuasai oleh pemerintah Hindia Belanda. Cilacap dan Nusakambangan waktu itu juga di bawah kekuasaan Pemerintah Hindia Belanda dipilih untuk pembuangan orang-orang yang dianggap melanggar hukum dan kekuasaan pemerintah Hindia Belanda.

Narapidana yang ada di Nusakambangan waktu itu belum diurus dengan baik oleh pemerintah Hindia Belanda. Mereka sering mengganggu penghuni Pulau Nusakambangan yang ada sebelum mereka datang, yaitu anak-anak keturunan Jaga Resmi dan Jaga Laut dan anak buahnya. Karena merasa terganggu mereka menyingkir dari Pulau Nusakambangan, dan membuat rumah-rumah tempat tinggal mereka di laut Segara Anakan. Rumah-rumah tersebut semakin lama semakin berkembang dan membentuk perkampungan.

Karena kampung-kampung itu berada di perairan laut (Segara Anakan), maka kemudian disebut Kampung Laut. Nama lain dari Kampung Laut adalah Bejagan atau Pejagan. Nama ini juga terkait dengan cerita bahwa Segara Anakan adalah tempat para prajurit kerajaan Mataram melakukan penjagaan agar daerah ini aman, bebas dari gangguan para bajak laut.

Waktu tempuh dengan perahu compreng menuju Kampung Laut selama dua jam dari pelabuhan Seleko Cilacap. Dari perahu compreng tersebut kita dapat menikmati keindahan hutan mangrove di sepanjang perjalanan. Pemandangan alam yang hijau dan indah dari pulau Nusa Kambangan. Selain itu juga kita bisa melihat dari dekat bangunan-bangunan LP di Nusa Kambangan.
Dan bisa di tempuh dari arah barat yaitu dari majingklak (ciamis) menggunakan perahu compreng.

Sumber: https://manatcinta.blogspot.com/2016/12/sejarah-kampung-laut-kabupaten-cilacap.html