Nama asal Sekolah Menengah Katholik ialah St. Francis Chinese High School. Sekolah ini ditubuhkan pas 1. 1. 58. Ketita sekolah ini ditubuhkan, sekolah hanya mempunyai 2 kelas peralihan dan 55 orang pelajar. Kebanyakan pelajar baru ini berasal dari Sekolah Rendah Katholik yang ditubuhkan terlebih dahulu. Kumpulan pelajar itu termasuk murid-murid lelaki dan perempuan.

Pada 1. 11. 58, Batu Asas sekolah telah diletakkan dengan rasminya oleh Tuan Yang Terutama Negeri Melaka, Tun Leong Ye Koh. Pada akhir tahun 1959 bangunan Blok A yang mempunyai 8 bilik darjah siap dibina. Semua perbelanjaan pembinaan sekolah ditanggung oleh oleh pihak gerja Katholik .

Pengasas sekolah ini ialah Rev. Fr. Louis Wee dan berikut adalah pengetua sekolah ini:

• Rev. Bro Valentin (1. 1. 58 - 31. 12. 58)
• Rev. Bro. Francis Kerk (1. 1. 59 - 31. 8. 60)
• Rev. Bro. Tien (1. 1. 60 - 31. 12. 65)
• Rev. Bro. Paul Auguste (1. 1. 66 - 31. 12. 66)
• Rev. Bro. Anthony Chen C.T. (1. 1. 67 - 17. 7. 69)
• Rev. Bro. Paut Clet (18. 7. 69 - 31. 12. 70)
• Rev. Bro. Paul Lim (1. 1. 71 - 28. 1. 74)
• Rev. Bro. Michael Lim (1. 3. 74 - 31. 12. 81)
• Rev. Bro. Anthony Chen C.Y. (1. 1. 82 - 31. 12. 83)
• Rev. Bro. Thomas Chin (1. 1. 84 - 31. 12. 95)
• En. Song Kuan Kong (1. 1. 96 - 16. 1.98)
• En, Tan See Boon (16. 1. 98 - sekarang)

Pada 1. 4. 61, nama sekolah ini ditukarkan menjadi SEKOLAH MENENGAH KATHOLIK, MELAKA.

Pada bulan Mac 1961, bangunan Blok B yang mengandungi 3 bilik darjah dan 3 bilik makmal sains siap dibina and di rasmikan oleh Chief Office, En. R. A. Wilson. Pelajar sekolah buat pertama kalinya menduduki Peperiksaan Lower Certificate of Education (LCE).

Pada tahun 1963 pelajar sekolah ini buat pertama kalinya menduduki Peperiksaan Cambridge School Certificate. Pada bulan Mac tahun itu, bangunan Block C yang mengandungi 9 bilik darjah and sebuah bilik perpustakaan siap dini.

Pada tahun 1973, sekolah ini terpaksa mengadakan kelas sesi pagi dan petang kerna bilangan pelajar telah bertambah. Pada tahun itu juga sekolah telah mempunyai Bendera Sekolah yang digunakan sehingga hari ini.

Pada bulan Disember 1985, blok banggunan baru 4 tingkat yang mengandungi bilik Pengetua, pejabat, bilik guru, bilik perpustakaan , bilik tayangan dan 8 bilik darjah mula dibina. Pembinaan bilik darjah sementera and debuah gelanggang bola keranjang dimulakan. Bangunan baru itu juga untuk digunakan bersama oleh Sek Rendah Katholik. Kos pembinaan ditanggung sebahagian besar oleh sumbangan orang ramai, Jawatankuas Bersama Sekolah, guru-guru dan pelajar-pelajar kedua-dua sekolah. PIBG dan Persatua Bekas Pelajar SMK untuk turut berusaha untuk mendapatan wang yang diperlukan.

Pada tahun 1988, semua kelas diadakan pada sebelah pagi kerana sekolah telah mempunyai bilik darjah yang cukup untuk menampung semua pelajar.

Pada akhir tahun 1992, bangunan Blok Bengkel Kemahairan Hiudp dan Kantin sekolah siap dibina. Bilik Tayangan dipindahkan ke Tingkat atas bangunan empat tingkat itu. Sebuah bilik Komputer telah juga dapat dijayakan dengan bantuan dan kerjasama PIBG.

Pada tahun 1994, sebuah kelas diubahsuai menjadi Bilik Bacaan berhawa dingin.