Sekolah Menengah Kebangsaan Kem Terendak dahulunya dikenali sebagai Slim High School Terendak Barracks.
Sekolah Menengah Kebangsaan Kem Terendak sebelum diambil alih oleh Kementerian Pelajaran Malaysia (Kerajaan Malaysia) pada tahun 1972, dikenali dengan nama Slim High School. Sekolah ini telah dirasmi pembukaannya pada 10 Februari 1965 oleh Brigadier Terence Douglas Herbert McMeekin, KCB, OBE. Sebelum tahun 1972, pentadbiran sekolah ini adalah di bawah kawalan dan selangaraan kerajaan Komanwel.
Kem Terendak di mana terletaknya sekolah ini, mula dibina pada bulan Jun 1957 bagi menempatkan Briged ke-28 Infantri Komanwel sehingga ke tahun 1969. Pada awal penubuhannya, kem ini mempunyai kekuatan 1 Battalion tentera British, 1 Battalion tentera Australia, 1 Battalion askar Melayu dan 1 Kompeni tentera dari New Zealand beserta unit-unit bantuan tempatan.
Malahan sehingga kini Sekolah Menengah Kebangsaan Kem Terendak ditadbir oleh dua kementerian, iaitu Kementerian Pertahanan Malaysia dan Kementerian Pelajaran Malaysia. Ciri inilah yang membezakannya dengan sekolah-sekolah lain di negeri ini.
Bentuk sekolah ini juga berbeza dengan sekolah-sekolah lain. Sekolah ini mempunyai lima bangunan dan terdapat sebuah dewan dan lima buah makmal sains. Bilik-bilik darjahnya kecil dan hanya boleh menampung antara 25-30 orang pelajar.
Pada mulanya semasa pentadbiran kerajaan Komanwel, dewan sekolah ini merupakan sebuah panggung wayang mini. Semasa peringkat awal pengambilalihan sekolah ini, semua bilik di bangunan utama dilengkapi dengan pendingin hawa tetapi kini diubah kepada kipas dinding sahaja. Ini kerana pengedaran ruang udaranya yang tidak begitu memuaskan.
Sekolah Menengah Kebangsaan Kem Terendak mempunyai dua buah asrama yang setiap satunya boleh menampung 100 orang pelajar. Kebanyakan penghuni asrama ini terdiri daripada anak-anak anggota tentera yang bertugas di luar negeri Melaka. Asrama Putera ditadbir oleh Kementerian Pertahanan Malaysia sementara Asrama Puteri ditadbir oleh Kementerian Pendidikan Malaysia.
Sekolah Kita Yang Jaya Gemilang Tekun Berusaha, Capai Cita-cita Cergas, Cekap dan Cemerlang Itulah Asas Pegangan Kita Sekolah Kita Kebanggaan Kita Nilai Murni Disemai Bersama Pada Agama, Bangsa dan Negara Menjadi Insan Yang Berguna Sekolah Kita Pastikan Berjaya Anak Perwira Gagah Setia Wawasan Negara Akan Terlaksana Menjadi Kebanggaan Semua
Lirik: En. Karim Bin Bayok
Lagu: En. Adam Bin Arshad.