Penubuhan dan pembinaan SMK Sook bermula pada tahun 1999 di atas tapak seluas 24 ekar dan terletak di pusat Pekan Kecil Sook, kira-kira 40 km dari Keningau dan siap sepenuhnya pada bulan April tahun 2001. pada 15hb Januari 2001, satu majlis dialog diadakan di antara PPD Keningau (En. Abd. Kadir Bin Bakri) dengan ibu bapa. Ianya berkaitan dengan desakan mereka dan pemimpin masyarakat tempatan bagi memulakan pengoperasian sekolah baru Sekolah Menengah Kebangsaan Sook. Walaupun belum siap sepenuhnya sekolah ini memulakan operasinya pada tanggal 5hb Februari 2001.

Seramai 8 orang guru telah merintis pembukaan sekolah ini yang terdiri daripada :

• En. Upilin @ Abd. Samad Bin Abd. Rahman (Pemangku Pengetua)
• En. Sahibin Warimin
• En. Suhailin Sharif
• En. Haspin Haris
• En. Kaslan Yusah
• En. Valerian Francis Anggi
• En. Aslinah Muhd. Shitin
• Pn. Veronica Wiliam Ibai

Seramai 132 orang murid telah memulakan sesi persekolahan pada tarikh yang sama. Dalam tempoh dua bulan, sekolah ini telah mencatat sejarahnya dengan menampilkan penyertaan sulung dalam kejohanan olahraga MSSD Keningau dan aktiviti Ko-Kurikulum yang lain. Sekolah Menengah Kebangsaan Sook menjadi sebutan dan kebanggaan kerana menjadi pusat bagi aktiviti-aktiviti kemasyarakatan, khususnya di Daerah Kecil Sook ini.

Sekolah Menengah Kebangsaan Sook telah siap sepenuhnya pada bulan April 2001. Majlis penyerahan kunci dan Bangunan telah dibuat pada 28hb April 2001 kepada En. Upilin @ Abd. Samad Bin Abd. Rahman oleh wakil dari pihak kontraktor. Turut hadir ialah Jurutera JKR dan Pegawai Pendidikan Bahagian (Tuan Hj. Mohd. Salleh Bin Hj. Wahab).

Sehingga 31hb Julai 2001, tenaga pengajar terus bertambah dan pada tarikh yang sama, Pengetua Sekolah Menengah Kebangsaan Sook yang pertama, En. Jaibet @ Johari Sabin telah memulakan tugasnya di sekolah ini.