Pembangunan Masjid Muhammad Cheng Hoo Indonesia dimulai tanggal 15 Oktober 2001, diawali dengan upacara peletakan batu pertama yang dihadiri oleh sejumlah tokoh Tionghoa Surabaya. Tokoh masyarakat Jawa Timur, Jajaran pengurus PITI dan Yayasan Haji Muhammad Cheng Hoo Indonesia.
Keunikan Masjid Muhammad Cheng Hoo Indonesia ini dilhami dari bentuk Masjid Niu Jie di Beijing yang dibanggun pada tahun 996 Masehi dengan luas tanah seluruhnya 3.070 meter.
Seiring dengan selesainya tahap pertema pembangunan Masjid ini pada tanggal 13 Oktober 2002, maka dilakukanlah peresmian pembangunan Masjid (Soft Opening) Muhammed Cheng Hoo Indonesia sudah dapat digunakan untuk beribadah dan selanjutnya tinggal melakukan beberapa penyempurnaan bangunan Masjid.
Oleh seluruh anggota Yayasan Haji Muhammad Cheng Hoo Indonesia dan PITI disepakati tanggal tersebut sebagai hari ulang tahun Yayasan dan Masjid Muhammed Cheng Hoo Indonesia. Diresmikan oleh Menteri Agama Republik Indonesia Prof. Dr. Said Agil Husin Al Munawar, MA di Surabaya pada, 28 Mei 2003
Secara keseluruhan Masjid Muhammad Cheng Hoo Indonesia berukuran 21 x 11 meter, dengan bangunan utama berukuran 11 x 9 meter. Pada sisi kiri dan kanan bangunan utama tersebut terdapat bangunan pendukung yang tempatnya lebih rendah dari bangunan utama.
Setiap bagian bangunan Masjid Muhammad Cheng Hoo Surabaya Indonesia ini memiliki arti tersendiri, misalnya ukuran bangunan utama. Panjang 11 meter pada bangunan utama Masjid Muhammad Cheng Hoo Surabaya ini menandakan bahwa Ka'bah saat pertama kali dibangun oleh Nabi Ibrahim AS memiliki panjang dan lebar 11 meter, sedangkan lebar 9 meter pada bangunan utama ini diambil dari keberadaan Walisongo dalam melaksanakan syi'at Islam di tanah Jawa.
Arsitekturnya yang menyerupai model kelenteng itu adalah gagasan untuk menunjukkan identitasnya sebagai muslim Tionghoa (Islam Tiongkok) di Indonesia dan untuk mengenang leluhur warga Tionghoa yang mayoritas beragama Budha.
Selain itu pada bagian atas bangunan utama yang berbentuk segi 8 (pat kwa), angka 8 dalam bahasa Tionghoa disebut Fat yang berarti jaya dan keberuntungan.
Dalam risalah, pada saat Rasulullah Muhammad SAW melakukan hijrah dari Mekkah ke Madinah, beliau dikejar-kejar oleh kaum kafir Quraish dan bersembunyi di dalam gua Tsur. Pada saat hendak memasuki gua tersebut, terdapat rumah laba-laba yang bentuknya seperti segi 8, Rasullullah yang dalam keadaan teraniaya tidak mau merusak rumah laba-laba tersebut.
Beliau memohon kepada Allah SWT agar diberikan perlindungan dan keselamatan dari kejaran kaum kafir Quraish. Dengan bantuan Allah SWT, Rasulullah dapat memasuki gua Tsur tanpa harus merusak rumah laba-laba tersebut. Saat situasi aman, beliau keluar dari gua Tsur dan melanjutkan perjalanan menuju Madinah untuk berhijrah guna menyampaikan wahyu yang diberikan Allah SWT kepada umat muslim di Madinah.