MRSM Terendak was established in cooperation between Majlis Amanah Rakyat (MARA) and the Ministry of Defence.

MRSM Terendak was inaugurated in 1993 by the Honourable Tun Ghafar Baba, who was then the Deputy Prime Minister of Malaysia.

MSRM Terendak at its inception was made up of a big rectangle building which is known as the Academic Building that consists of 18 classrooms, a Teacher Work Room (Malay: Bilik Kerja Guru (BKG)), an Education Resource Centre (library) (Malay: Pusat Sumber Pembelajaran (PSP)), science labs, a gymnasium, and other rooms.

At the centre of the Academic Building is a large hall named Malay: Dewan Budiman that can accommodate 700 people at one time.

The current student dining hall is adjacent to block E, and it is called Malay: Teres Teratai or Lotus Terrace.