Gagasan mengenai pembentukan organisasi khusus bagi mahasiswa Nahdliyin telah muncul sebelum berdirinya Pergerakan Mahasiswa Islam Indonesia (PMII) pada 1960. Pada masa itu, mahasiswa Nahdliyin masih banyak berada dalam wadah Ikatan Pelajar Nahdlatul Ulama (IPNU) yang berdiri pada 1954. Seiring bertambahnya jumlah anggota IPNU yang telah berstatus mahasiswa, muncul kebutuhan untuk memiliki wadah yang secara khusus dapat menampung kehidupan dan aktivitas mahasiswa.
Upaya membentuk organisasi mahasiswa Nahdlatul Ulama kemudian muncul dalam bentuk organisasi-organisasi lokal. Di Jakarta, pada Desember 1955, sejumlah aktivis menggagas pembentukan Ikatan Mahasiswa Nahdlatul Ulama (IMANU). Pada tahun yang sama juga terdapat Keluarga Mahasiswa Nahdlatul Ulama (KMNU) di Surakarta. Sementara itu, di Bandung muncul Persatuan Mahasiswa Nahdlatul Ulama (PMNU). Organisasi-organisasi tersebut menunjukkan bahwa gagasan mengenai wadah mahasiswa NU telah berkembang di beberapa kota sebelum PMII berdiri.
Namun, keberadaan organisasi mahasiswa tersebut belum berkembang menjadi satu organisasi mahasiswa NU berskala nasional. Salah satu persoalannya adalah IPNU masih merupakan organisasi yang relatif baru, sehingga terdapat kekhawatiran bahwa pembentukan organisasi mahasiswa tersendiri akan memengaruhi perkembangan IPNU. Selain itu, sejumlah pengurus IPNU pada masa tersebut juga telah berstatus sebagai mahasiswa. Karena pertimbangan tersebut, upaya membentuk organisasi mahasiswa NU belum memperoleh dukungan yang cukup untuk berkembang.
Gagasan tersebut kembali menguat setelah IPNU berkembang. Dalam Muktamar III IPNU di Cirebon pada 27–31 Desember 1958, diputuskan pembentukan Departemen Perguruan Tinggi IPNU yang dipimpin oleh Ismail Makky. Departemen ini dibentuk untuk mewadahi anggota IPNU yang telah berstatus mahasiswa. Dalam sejumlah sumber sejarah PMII, Departemen Perguruan Tinggi IPNU kemudian disebut sebagai salah satu cikal bakal langsung lahirnya PMII.
Pembentukan departemen tersebut belum sepenuhnya menyelesaikan persoalan. Kehidupan mahasiswa dinilai memiliki kebutuhan dan dinamika yang berbeda dengan pelajar. Selain itu, Departemen Perguruan Tinggi IPNU memiliki keterbatasan dalam ruang geraknya karena tidak dapat menjadi anggota Persatuan Perhimpunan Mahasiswa Indonesia (PPMI), sebuah konfederasi organisasi mahasiswa yang pada masa itu menghimpun organisasi-organisasi mahasiswa.
Perkembangan berikutnya terjadi dalam Konferensi Besar IPNU di Kaliurang, Yogyakarta, 14–17 Maret 1960. Dalam forum tersebut kembali dibahas kebutuhan akan organisasi mahasiswa NU yang berdiri terpisah dari IPNU. Konferensi kemudian memutuskan perlunya membentuk organisasi mahasiswa NU yang terpisah secara struktural dan administratif dari IPNU-IPPNU. Keputusan inilah yang menjadi tahap penting sebelum dilaksanakannya musyawarah mahasiswa NU di Surabaya pada April 1960.
Dengan demikian, sebelum PMII lahir pada April 1960, telah terdapat serangkaian proses kelembagaan dan gagasan: munculnya organisasi mahasiswa NU di sejumlah daerah, pembentukan Departemen Perguruan Tinggi IPNU pada 1958, hingga keputusan Konferensi Besar IPNU pada Maret 1960 untuk membentuk organisasi mahasiswa NU yang berdiri sendiri. Rangkaian inilah yang kemudian mengantarkan pada proses kelahiran PMII.