Sekolah ini yang pada mulanya dikenali sebagai Sekolah Menengah Sains Pulau Pinang (SMSPP- telah diguna semenjak 1973, tetapi telah digunapakai oleh Sekolah Menengah Sains Pasir Putih), telah ditubuhkan pada tahun 1973. Disebabkan bangunan sekolah masih dalam proses pembinaan, maka pelajar-pelajar sekolah ini telah ditumpangkan di beberapa buah sekolah lain iaitu Sekolah Menengah Penang Free (Tingkatan Empat – Lelaki), Sekolah Menengah Perempuan St. George (Tingkatan Empat – Perempuan) dan Sekolah Menengah Kampung Bahru (Tingkatan Satu – Lelaki dan Perempuan). Setelah bangunan sekolah siap sepenuhnya pada awal 1974, barulah pelajar-pelajar dipindahkan ke sekolah ini.

Pembinaan bangunan SMSTSSS bermula sejak penghujung tahun 1972 lagi. Ia dibina atas bekas kawasan ladang getah (Ladang Getah Alma) seluas 30.2 ekar dengan perbelanjaan kira-kira RM 2.3 juta. Dalam Rancangan Malaysia Keempat, sebanyak RM 5 juta lagi telah diperuntukkan untuk sekolah ini bagi kerja-kerja pembinaan bangunan tambahan dan pembelian tanah seluas 19.9 ekar, bagi membolehkan ia berkembang sesuai sebagai sebuah sekolah berasrama penuh. Pada 14 Januari 1974, barulah bangunan-bangunan sekolah siap dibina dan diserahkan secara rasmi kepada pihak pentadbir sekolah oleh Jabatan Kerja Raya.

Pengambilan pelajar-pelajar bermula pada awal tahun 1973. Mereka merupakan pelajar-pelajar perintis sekolah ini yang berasal dari negeri-negeri seperti Pulau Pinang, Perak, Kelantan, Terengganu, N.Sembilan, Pahang, Melaka, Selangor dan Sabah. Jumlah pelajar perintis ini adalah kira-kira 380 orang. Sementara guru-guru yang ditugaskan sejumlah 19 orang. Pada tahun 1974, jumlah pelajar telah bertambah menjadi 615 orang iaitu dengan kemasukan pelajar-pelajar Tingkatan Satu dan Empat yang baru. Serentak dengan itu juga bilangan guru juga turut bertambah menjadi 43 orang.

Pada tahun 1975, barulah sekolah ini mempunyai pelajar-pelajar dari semua tingkatan bermula dari Tingkatan Satu hingga ke Tingkatan Enam Rendah dengan jumlah seramai 752 orang pelajar dan dibantu oleh 45 orang guru.

Pada tahun 1977, SMSTSSS mula menempatkan pelajar-pelajar Matrikulasi Universiti Sains Malaysia, Pulau Pinang seramai 101 orang. Dengan itu juga, SMSTSSS tidak lagi menawarkan kelas Tingkatan Enam kepada pelajar-pelajarnya. Mulai 1996, SMSTSSS juga telah memulakan aliran teknikal iaitu dengan menawarkan mata pelajaran Teknologi Kejuruteraan dan Lukisan Kejuruteraan. Dalam tahun yang sama juga, mata pelajaran Bahasa Perancis mula diperkenalkan kepada pelajar-pelajar Tingkatan Satu.

Pada 2 April 1982, tepat jam 4.30 petang, bermulalah satu lagi detik yang cukup bersejarah bagi sekolah ini kerana saat itu telah berlangsungnya upacara perasmian pembukaan sekolah ini serta penukaran nama barunya iaitu Sekolah Menengah Sains Pulau Pinang kepada Sekolah Tun Syed Sheh Shahabudin. Upacara tersebut telah disempurnakan oleh Yang Berhormat Dato’ Dr. Sulaiman bin Haji Daud, Menteri Pelajaran Malaysia ketika itu.

Pada tahun 1995 , perkataan sains telah ditambah kepada nama sekolah ini manjadi Sekolah Menengah Sains Tun Syed Sheh Shahabudin seperti yang dikenali sekarang ini. Pada 11 Mei 1997, sebuah persatuan bekas-bekas pelajar SMSPP, STSSS dan SMSTSSS telah ditubuhkan secara rasminya.

Antara tenaga peneraju utama SMSTSSS (SMSPP ketika itu) ialah Encik Marmuji bin Koso. Beliau memulakan perkhidmatannya pada awal 1974 selepas Encik Harun bin Hassan bertukar pada 1 Februari 1974. Pada 15 Ogos 1976, teraju kepimpinan SMSTSSS telah diambil alih oleh Tuan Haji Mohd. Arif bin Rahmat. Jawatan Pengetua kemudiannya telah disandang oleh Tuan Haji Halim bin Othman pada 16 Julai 1982. Mulai 1 Disember 1990 pula, jawatan Pengetua telah disandang oleh Tuan Haji Wan Min bin Wan Din. Seterusnya mulai 16 Disember 1994, kepimpinan SMSTSSS telah diterajui oleh Tuan Haji Zainuddin bin Haji Abdul Kadir. Kemudiannya jawatan pengetua telah disandang oleh Tuan Haji Ngazizan bin Haji Din, mulai 16 November 1995. Pada 1 Februari 1999 jawatan Pengetua tersebut telah disandang pula oleh Encik Ibrahim bin Mohamad sehingga Disember 2004.

Encik Umar bin Man seterusnya mengambilalih jawatan pengetua SMSTSSS sehingga Julai 2006. Selepas persaraannya, Encik Baharuddin bin Osman telah menerima mandat seterusnya sebagai pengetua. Beliau mempunyai sejarahnya yang tersendiri kerana beliau merupakan bekas pelajar SMSTSSS yang pertama kembali ke sekolah sebagai pengetua. Pada tahun 2009, Tuan Haji Mohd Noor bin Yusof, yang dahulunya pernah memegang jawatan sebagai Penolong Kanan Hem SMSTSSS, telah menggantikan Encik Baharuddin bin Osman sebagai Pengetua.Kini,pengetua SMSTSSS ialah Tuan Haji Jamaludin bin Yaacob.