Setelah serangkaian diskusi mengenai masa depan politik Islam, timbul gagasan untuk mendirikan organisasi politik. Pada Oktober 1945, sebuah komite dikepalai Natsir dibentuk untuk merealisasikan rencana tersebut. Tak lama, Wakil Presiden Mohammad Hatta mengeluarkan Maklumat No X tentang anjuran membentuk partai-partai politik.
Natsir bergerak cepat. Pada 7-8 November 1945, di Gedung Madrasah Mu’alimin Muhammadiyah Yogyakarta, dihelatlah Kongres Umat Islam yang dihadiri para pemimpin muslim dan perwakilan organisasi muslim. Kongres memutuskan pembentukan satu-satunya partai politik yang menyalurkan aspirasi politik umat Islam.
Baca juga: Lakon Masyumi Zaman Revolusi
Peserta kongres memilih nama Masyumi, tapi bukan merujuk pada Majelis Syuro Muslimin Indonesia di masa Jepang, ketimbang nama lain yang diusulkan, Partai Rakyat Islam. Sukiman Wirjosandjojo, ketua kongres, terpilih sebagai ketua umum.
Sebagaimana disebutkan dalam Anggaran Dasar, Masyumi memiliki tujuan: terlaksananya ajaran dan hukum Islam dalam kehidupan orang-seorang, masyarakat, dan negara Republik Indonesia, menuju keridhaan Illahi.
Beberapa organisasi yang di masa Jepang berafiliasi dengan Masyumi menjadi anggotanya. Organisasi Islam lainnya kemudian ikut bergabung. Selain organisasi, Masyumi menerima anggota perorangan. Dualisme keanggotaan ini didasarkan pertimbangan untuk memperbanyak anggota dan “agar Masyumi dapat dilihat sebagai wakil umat, tanpa ada yang merasa tidak diwakili,” tulis Deliar Noer dalam Partai Islam di Pentas Nasional.
Baca juga: Dua Faksi Partai Masyumi
Dengan sistem keanggotaan semacam itu, banyak yang memprediksikan bahwa Masyumi akan memenangi pemilihan umum. Namun, sistem ini juga punya kelemahan. Sistem ini, menurut George McT Kahin dalam Nasionalisme dan Revolusi di Indonesia, menjadikan Masyumi “partai politik terbesar di Indonesia tapi kurang terorganisasi” atau dalam istilah Sjafruddin Prawiranegara, ketua terkemukanya “seekor gajah yang mengidap beri-beri”.
Baca juga: Ketika Masyumi Memimpin Kabinet