Pada asalnya, Sekolah Menengah Kebangsaan Raja Tun Uda (SMKRTU) ini dikenali sebagai Sekolah Menengah Kebangsaan Bayan Lepas, Pulau Pinang (SMKBL) dan ia bermula pada 1963. Ketika itu, sekolah ini menumpang bangunan Sekolah Rendah Inggeris Bayan Lepas yang dirasmikan oleh Tan Sri Khir Johari sebagai Menteri Pelajaran dan Pengerusi Lembaga Pengelola sekolah itu Allahyarham Tuan Haji Azyze. Beliau merupakan Yang Dipertua Majlis Luar bandar Pulau Pinang.

Pengetua Pertama ialah Master Kamil Hassan.   Pada tahun 1964, jumlah pelajar di SMKBL ketika itu hanyalah 240 orang sahaja. Tenaga pengajarnya pula seramai 10 orang  di bawah pimpinan Encik Fadzil B. Jaafar selaku pengetua ketika itu. Pelajar-pelajar yang belajar di SMKBL ini adalah dari Daerah Barat Daya yang meliputi Bayan Lepas,Batu Maung,Teluk Kumbar, Sungai Ara, Sungai Nibong, dan juga pelajar-pelajar dari kawasan Gelugor dan Balik Pulau, Pulau Pinang.

 SMKBL ini merupakan  Sekolah Menengah Kebangsaan yang pertama sekali dibina di Daerah Barat Daya Pulau Pinang ini. Pada masa yang sama (dalam tahun 1964), bangunan baru SMKBL sedang dalam Sekolah Menengah Kebangsaan Raja Tun Uda pembinaan dan  terletak berhampiran dengan Sekolah Inggeris Bayan Lepas bagi menampung bilangan pelajar yang dijangkakan meningkat. Pembinaan sekolah baru diperlukan kerana pada tahun yang sama juga iaitu 1964 di mana Sistem Pendidikan Malaysia telah berubah iaitu peperiksaan masuk ke Tingkatan Tiga adalah secara automatik. Langkah ini adalah selaras dengan cita- cita kerajaan ingin memberi pendidikan umum sekurang kurangnya 9 tahun kepada semua kanak-kanak.

 Sekolah aneka jurusan telah mengambil tempat bagi menggantikan sistem lama dalam  Sistem Pendidikan Malaysia pada tahun 1965 dan sistem ini telah mengakibatkan bilangan pelajar meningkat. Untuk mengatasi masalah kekurangan bilik darjah ketika itu,SMKBL terpaksa menumpang di dua buah sekolah iaitu Sekolah Kebangsaan Bayan Lepas dan Sekolah Agama Sungai Ara bagi menampung pelajar-pelajar berlebihan.

Pada pertengahan tahun 1965, bangunan baru SMKBL telah disiapkan dan boleh digunakan sepenuhnya. Pada 20hb Julai 1965, bangunan SMKBL telah dibuka dengan rasminya oleh Yang Berhormat  Menteri Pendidikan, Encik Mohd. Khir Johari dan nama SMKBL telah ditukar kepada Sekolah Menengah Kebangsaan Raja Tun Uda (SMKRTU). Pengetua pertama ialah Allahyarham Encik Mohamad Kamil bin Hassan dan Penolong Kanan ialah Cikgu Fadzil bin Jaafar. SMKRTU dapat menampung keperluan sistem aneka jurusan dalam pelbagai bidang iaitu Bidang Bahasa, Bidang Kemanusiaan, Bidang Teknik dan vokasional dan Bidang Sains dan Matematik.  

Nama SMKRTU dipilih sempena nama Gabenor Pertama Pulau Pinang iaitu Raja (Sir) Tun Uda Al-Haj bin Raja Muhammad (1894 - 17 Oktober 1976). Memandangkan Lapangan Terbang Bayan Lepas telah dinaikkan tarafnya kepada Lapangan Terbang Antarabangsa Bayan Lepas, maka kedudukan SMKRTU ini tidak sesuai lagi dan terpaksa dipindahkan ke Jalan Tengah Bayan Lepas dengan keluasan tapaknya 12.6 ekar pada awal tahun 1983.  Pada tahun 1987, SMKRTU telah memulakan pelajaran Tingkatan Enam bagi Aliran Sains dan bilangan pelajar yang mengikuti Kelas Tingkatan Enam Sains ketika itu seramai 19 orang pelajar yang terdiri daripada pelajar-pelajar sekolah lain,di samping pelajar-pelajar sekolah ini sendiri. Pada 30 November 2015, Tingkatan Enam di SMKRTU telah ditutup secara rasmi dan berpindah ke Sekolah Menengah Sungai Ara di bawah Pentadbiran Pengetua Sekolah Menengah Sungai Ara iaitu Encik Ridza bin Hussin dan  Penolong Kanan Tingkatan 6, Encik Kumaravel a/l Subramaniam.

Pada tahun 2020, jumlah pelajar SMKRTU telah mencecah 1,419 pelajar dengan bilangan tenaga pengajar seramai 120 orang di bawah pimpinan Pengetua Haji Mohamad Shukor Bin Zakariah.