SESMA memulakan sesi pengajiannya pada Januari 1973 dengan menumpang di Sekolah Menengah Padang Midin, Kuala Terengganu. Para pelajar pula ditempatkan di Asrama Yayasan Terengganu, Jalan Negara, Kuala Terengganu. Pada Oktober 1974, bangunan baru bertempat di Mukim Wakaf Tembesu mula digunakan dan dikenali sebagai Sekolah Menengah Sains Terengganu (SMST).

Pembukaan rasmi sekolah telah dilakukan oleh DYMM Sultan Ismail Nasiruddin Shah ibni Almarhum Sultan Zainal Abidin pada 5 September 1979. Pada 18 September 1982 sekolah bertukar nama kepada Sekolah Sultan Mahmud Kuala Terengganu yang mana upacara perasmiannya disempurnakan oleh DYMM Sultan Mahmud Al Muktafi Billah Shah Ibni Almarhum Sultan Ismail Nasiruddin Shah. Pada tahun 1995 sekolah ini sekali lagi diberi nama baru, Sekolah Menengah Sains Sultan Mahmud (SESMA), Kuala Terengganu yang menjadi gambaran betapa pentingnya mata pelajaran sains dalam kurikulum sekolah masa kini.

Pengetua pertama ialah Tuan Hj Muhammad Bin Mustaffa sementara En. Johari Shamsuddin sebagai Penolong Kanan. Kumpulan pelajar perintis seramai 109 orang terdiri daripada 51 orang lelaki dan 58 orang perempuan dengan 5 orang guru lelaki dan 2 orang guru perempuan. Pada tahun 1978, pengambilan pertama pelajar kelas Matrikulasi seramai 90 orang yang dikelolakan oleh Universiti Kebangsaan Malaysia (UKM) telah diadakan. SESMA mula memasuki era digital apabila menjadi salah sebuah Sekolah Bestari di bawah rancangan pembangunan Kementerian Pendidikan pada tahun 1999.

Pelajar-pelajar di SESMA mengikuti pelajaran dalam beberapa aliran. Di peringkat Menengah Atas, hanya aliran sains tulen disediakan. Bermula dari tahun 1989, mata pelajaran kemahiran hidup diperkenalkan untuk menggantikan pelajaran seni perusahaan dan sains rumah tangga. Kelas komputer diwajibkan kepada pelajar tingkatan satu hingga empat. Mata pelajaran Bahasa Perancis mula diperkenalkan pada tahun 1996 kepada pelajar menengah rendah manakala Bahasa Jepun pada tahun 1997.

Kemudahan pengajaran dan pembelajaran adalah mencukupi. Selain kemudahan makmal sains, bengkel kemahiran hidup, bilik ERT dan perpustakaan terdapat kemudahan-kemudahan tambahan seperti makmal bahasa, bilik komputer, makmal Multimedia dan Pusat Sumber. Dari semasa ke semasa, pihak sekolah akan menambah lagi kemudahan-kemudahan tersebut untuk faedah pelajarnya.