Berdasarkan Babad Banyumas, pembangunan Benteng Pendem dilaksanakan oleh Sunan Paku Buwono IV untuk keperluan menghadapi bajak laut yang sering menyerang pantai. Terdapat kemungkinan sebelum dibangun oleh Belanda, dahulunya telah terdapat banteng. Pada awalnya nama banteng yang asli tidak ditemukan sehingga masyarakat sekitar menamakan banteng ini Benteng Pendem. Pemberian nama ini kemungkinan karena banteng ini dibangun dibawah permukaan tanah.
Benteng yang selanjutnya dibangun Pemerintahan Belanda ini diperkirakan difungsikan sejak tahun 1879. Benteng Pendem merupakan pusat pertahanan sedangkan banteng-benteng lainnya seperti Benteng Karangbolong dan banteng-benteng yang berada di Pulau Nusakambangan sebagai bagian dari banteng pusat.
Pendirian banteng ini oleh Belanda hanpir bersamaan dengan masa Tanam Paksa yang dicanangkan oleh Gubernur Jenderal Johannes Van Den Bosch. Pada saat itu Cilacap memang menjadi pelabuhan yang penting untuk mengangkut hasil perkebunan hasil tanam paksa dari Yogyakarta dan Purworejo. Pada masa jayanya, Pelabuhan Cilacap pernah bersaing dengan Pelabuhan Semarang karena daerah Jawa Barat dan Jawa Tengah Selatan selalu mengirimkan hasil bumi melalui pelabuhan ini. Fakta ini mengakibatkan pelabuhan ini sangat strategis bagi Belanda dalam rangka mengamankan kegiatan ekspor hasil bumi yang menyumbang dana yang berlimpah bagi negara Belanda. Pelabuhan Cilacap menjadi sepi karena jalan darat di daerah pedalaman mulai dibangun jalur kereta api maupun jalan Pelabuhan yang banyak dipakai adalah Pelabuhan Semarang.
Berdasarkan berbagai sumber menyebutkan bahwa penggunaan banteng oleh Belanda sampai dengan tahun 1942 yaitu saat penyerahan kekuasaan Belanda kepada Jepang. Selanjutnya antara tahun 1952-1962 benteng ini dimanfaatkan oleh pasukan RPKAD sebagai tempat latihan tempur dan pendaratan laut. Pada tahun 1986, Pemerintah Daerah mengembangkan benteng ini sebagai objek wisata.
Benteng Pendem terletak di Dusun Kebonjati, Desa Cilacap, Kecamatan Cilacap, Kabupaten Cilacap Propinsi Jawa Tengah. Pada saat ini halaman dalam banteng telah dibangun beberapa fasilitas pariwisata sedangkan halaman luar berdekatan dengan kilang minyak milik Pertamina. Lokasi benteng ini juga berdekatan dengan pantai Teluk Penyu yang cukup terkenal di Cilacap. Dilingkungan luar banteng juga terdapat makam orang-orang Belanda seperti makam PH.M. Regena Berg istri JN Langaar, asisten Residen Cilacap yang meninggal 22 Mei 1909. Letak Benteng Pendem juga berhadapan dengan Pu;au Nusakambangan yang juga terdapat beberpa banteng lain.
