Sekolah Menengah St. Michael ditubuhkan pada 5 Oktober 1888.

Pengasas sekolah iaitu Rev. William Henry Elton menjadi guru pertama yang mengajar di sekolah tersebut. Pada masa itu, jumlah pelajar hanya seorang sahaja. Keadaan ini berterusan selama 2 bulan. Walaubagaimanapun, jumlah pelajar telah bertambah dari sebulan demi sebulan.

Pada tahun-tahun berikutnya, sekolah ini menunjukkan kemajuan yang lembap. Ini disebabkan kekerapan sekolah menukar pengetuanya. Masalah ini telah diatasi dengan anak sulung Rev. Elton ditugaskan sebagai pengetua pada tahun 1901. Beliau memegang jawatan tersebut untuk 12 tahun.

Pada 31 Oktober 1904, bandar Sandakan dilanda puting beliung yang menyebabkan kemusnahan sekolah. Rev. Elton telah berusaha untuk mendapatkan bangunan baru sekolah. Bangunan 2 tingkat telah berjaya didirikan pada April1907. Bangunan ini bertahan sehingga Perang Dunia Pertama.

Anak sulung Rev. Elton iaitu Mr. Henry Elton meletak jawatan pada tahun 1913 disebabkan masalah kesihatan. Ini menandakan tamatnya "ERA ELTON" untuk sekolah ini. Selepas itu, terdapat beberapa orang lagi yang menjadi pengetua sekolah sebelum Perang Dunia Kedua.

Semasa penjajahan Jepun di Borneo Utara, sekolah ini telah ditutup dan dijadikan sebagai Pusat Perhubungan untuk orang-orang Jepun sehingga peristiwa kebakaran pada tahun 1945.

Selepas Perang Dunia Kedua, Mr. Fu Yun Fatt merupakan salah seorang guru sekolah ini telah berusaha untuk membina kembali Sekolah St. Michael. Sekolah ini berjaya didirikan semula pada bulan Mei 1946.

Bermula dari tarikh tersebut, SMK St. Michael telah mengalami pelbagai perubahan dari segi fizikal, tenaga pengajar dan jumlah pelajarnya. Bangunan lama ditukarkan dengan bangunan baru, jumlah tenaga pengajar semakin bertambah dan jumlah pelajar juga semakin meningkat. Keadaan ini berterusan sehingga hari ini.

Pada hari ini, SMK St. Michael di bawah pentadbiran pengetuanya, En. Henley Liew Yun Ye telah berjaya menempuh cabaran alaf baru. Cabaran-cabaran masalah disiplin, masalah akademik, bukan akademik, ledakan maklumat teknologi terkini dan sebagainya telah berjaya diatasi dengan usaha gigih. Atas usaha persatuan Murid Tua dan inisiatif pengetua sendiri, sekolah telah mengalami banyak perubahan. Perubahan yang utama adalah pertambahan satu tingkat baru kepada bangunan utama sekolah dan pembaikan bangunan lama sekolah.