SMK Sultan Alauddin mula dibina pada tahun 1969 dan siap pembinaan pada tahun 1970. Pada awalnya sekolah ini dikenali dengan nama Sekolah Menengah Rendah Kebangsaan Bukit Besar. Nama sekolah ini kemudiannya ditukar kepada Sekolah Sultan Alauddin sesuai dengan nama pengasas Kesultanan Johor yang menyambung kewibawaan Kesultanan Melayu Melaka yang berhijrah ke negeri Johor pada abad ke-16.

Pada tahun 1970, murid sekolah ini menumpang sementara di SK Bukit Ramun. Penyelia pertama SMK Sultan Alauddin ialah En. Jamian bin Hj. Nawawi. Secara rasminya, SMK Sultan Alauddin telah dibuka pada tahun 1971 yang mengandungi 9 buah kelas, 14 orang guru dan 359 orang murid. Sekolah ini mencapai kemuncak populasinya pada tahun 1980 iaitu 52 buah kelas, 78 orang guru dan 2130 orang murid. Bermula pada tahun 1985 hingga sekarang bilangan murid semakin berkurangan kerana ramai peneroka yang telah meningkat usia dan meninggal dunia. Kini hampir semua murid SMK Sultan Alauddin terdiri daripada generasi kedua dan ketiga Felda di Gugusan Taib Andak.

Semasa mula beroperasi, SMK Sultan Alauddin hanya mempunyai sebuah bangunan untuk menempatkan bilik darjah dan sebuah lagi bangunan menempatkan makmal sains, bilik sains rumahtangga, sebuah makmal pertanian dan sebuah kantin. Pada tahun 1978, sekolah inin mempunyai cawangannya di Bandar Tenggara hingga tahun 1982. Cawangan SMK Sultan Alauddin di Bandar Tenggara kemudiannya beroperasi sendiri dan diberi nama SMK Bandar Tenggara.

Pada peringkat awal, SMK Sultan Alauddin di bawah pentadbiran PPD Kota Tinggi. Bermula pada tahun 1984 setelah wujudnya PPD Kulai, segala aktiviti dan pentadbirannya berpindah ke PPD Kulai disebabkan SMK Sultan Alauddin terletak berhampiran dengan Bandar Kulai. SMK Sultan Alauddin berkeluasan 13.5 ekar 2 R dan 16 P yang terletak di lot tanah 3474 Mukim Hulu Sungai Johor. Pembangunan fizikal rancak dilaksanakan di SMK Sultan Alauddin, antaranya seperti berikut:

• 1976: Sebuah Dewan Besar (Dewan SEMESTA)
• 1978: Sebuah bangunan tiga tingkat dan dua makmal sains.
• 1981: Sebuah bangunan baru menempatkan Pusat Sumber, makmal Biologi, Kimia dan Fizik.
• 1981: Sebuah bangunan pasang siap.
• 1990: Sebuah bangunan empat pintu melalui konsep gotong-royong yang menempatkan Bilik Kaunseling, Bilik rawatan, SPBT dan sebuah kelas.
• 2003: Sebuah makmal komputer.
• 2011: Dua buah bangunan empat tingkat dan sebuah bangunan dua tingkat.

Kini, SEMESTA mempunyai 28 buah kelas, 6 makmal sains, sebuah pusat sumber, bengkel kemahiran hidup (kerja kayu, jahitan, kerja paip, elektrik dan elektronik), surau At-Taufiq, bilik kebal untuk kegunaan PPD Kulaijaya, bilik lukisan kejuruteraan, bilik reka cipta, Studio Seni Visual, bilik rawatan, bilik SPBT, bilik akses, koperasi, padang, gelanggang serbaguna, kantin, bilik unit bimbingan/kaunseling juga menempatkan bilik pameran anti dadah. Perkembangan prasarana semakin lengkap apabila 2 blok bangunan menempatkan bilik mesyuarat, pejabat pentadbiran, dan beberapa bilik darjah yang mula beroperasi sepenuhnya pada tahun 2011 iaitu Blok A dan B.

Dalam usaha meningkatkan taraf prasarananya, SMK Sultan Alauddin telah mendapat peruntukan pembinaan 3 blok bangunan yang terdiri daripada 2 blok 4 tingkat dan 1 blok 2 tingkat. Pembinaannya telah bermula pada awal Jun 2009 dan mula digunakan pada Julai 2011.