Sekolah Menengah Kebangsaan Telok Mas (SMKTM) mula dibina pada bulan Jun 2000 di atas sebidang tanah seluas 6.32 hektar di kawasan Telok Mas di bawah DUN Alai. Sekolah ini terdiri daripada 4 blok utama iaitu Blok A (pentadbiran), Blok B (bilik darjah), Blok C (makmal sains) dan Blok D (bengkel dan pusat sumber). SMK Telok Mas juga menyediakan kemudahan asrama untuk pelajar-pelajar lelaki dan perempuan dengan kapasiti maksimum 400 orang pelajar.

Bermula dengan 9 buah kelas Tingkatan 1 dan 3 buah kelas Tingkatan 2. Pelajar Tingkatan 1 terdiri daripada kumpulan pertama pelajar Rancangan Khas (RK) seramai 160 orang dan selebihnya pelajar Rancangan Biasa. Pelajar Tingkatan 2 pula terdiri daripada pelajar-pelajar yang asalnya bersekolah di SMK Seri Mahkota dan SMK Ayer Molek. Jabatan Pelajaran Negeri Melaka juga telah menempatkan seramai 5 orang pelajar Rancangan Khas Sukan (RKS).

Pelajar Rancangan Khas (RK) terdiri daripada pelajar yang mendapat keputusan UPSR yang cemerlang dan memuaskan tetapi gagal untuk mendapat tempat di Sekolah Berasrama Penuh (SBP), Maktab Rendah Sains MARA (MRSM) atau Sekolah Berasrama Penuh Integrasi (SBPI). Pelajar-pelajar ini akan ditempatkan di asrama sekiranya terpilih, manakala pelajar Rancangan Biasa (RB) terdiri daripada pelajar yang tinggal berhampiran dengan sekolah dan mendapat keputusan UPSR sekurang-kurangnya 3A 2C untuk bersekolah di sekolah ini.

Atas persetujuan orang ramai, Kerajaan Negeri Melaka telah mempertimbangkan permohonan tersebut untuk membiayai yuran makan dan minum pelajar-pelajar Rancangan Khas yang ditempatkan di asrama sebanyak RM1.00 seorang (sehari) bermula pada tahun 2002 sehinggalah kini.

Berdasarkan keputusan Majlis Mesyuarat Kerajaan Negeri Melaka (EXCO) pada 28 Februari 2001 dan disahkan pada 14 Mac 2001 keputusan telah dibuat untuk menjadikan SMK Telok Mas sebagai sekolah berasrama kerajaan negeri Melaka.

SMK Telok Mas telah mendapat perhatian yang jitu dari kerajaan negeri, Jabatan Pelajaran Melaka, Pejabat Pelajaran Daerah dan masyarakat setempat atas kecemerlangan yang dicapai bertahun lamanya. Buat kali pertama SMK Telok Mas telah diwarwarkan di akhbar Berita Harian pada 20 Mei 2001.