Berdirinya Fatayat NU tidak bisa dilepaskan dari sejarah berdirinya Nahdlatul Ulama (NU) sebagai organisasi induknya, dan sejarah Indonesia sebagai tanah airnya. Penjajahan selama bertambah-tahun telah menyebabkan bangsa Indonesia terpuruk. Perjuangan melawan keterbelakangan, kemiskinan, kebodohan, dan keterpurukan akibat penjajahan ini kemudian mengkristal dan membangkitkan semangat kembali di seantero negeri hingga mencapai puncaknya pada tahun 1908 yang dikenal sebagai tahun Kebangkitan Nasional. Kalangan pesantren merespons semangat ini dengan membentuk berbagai pergerakan organisasi, seperti Nahdlatul Wathan (Kebangkitan Tanah Air) pada tahun 1916, Taswirul Afkar atau dikenal juga dengan Nahdlatul Fikri (Kebangkitan Pemikiran) pada 1918 yang bergerak di bidang politik sosial,
Sementara itu, di Arab Saudi terjadi perkembangan yang cukup penting di mana Raja Ibnu Saud ingin menjadi Madzhab Wahabi di Mekah sebagai asas tunggal dan memerlukan ingin semua peninggalan sejarah Islam atau Pra-Islam yang selama ini kerap diziarahi karena dianggap sebagai bid’ah. Perkembangan ini mengundang baik oleh kelompok modernis di Indonesia, baik oleh pimpinan Muhammadiyah pimpinan oleh Ahmad Dahlan, maupun oleh PSII (Partai Sarekat Islam Indonesia) pimpinan HOS Cokroaminoto. Menolak kalangan pesantren menolaknya.
Perbedaan sikap ini menyebabkan dikeluarkannya anggota Kongres al-Islam di Yogyakarta pada tahun 1925 dan tidak dilibatkan dalam Mu’tamar ‘A’lam Islami (Kongres Islam Internasional) di Mekkah yang akan mengesahkan keinginan Raja tersebut. Kalangan Pesantren kemudian membuat delegasi sendiri bernama Komite Hejaz yang diketuai oleh KH. Wahab Hasbullah. Atas desakan kalangan pesantren yang diwakili oleh Komite ini dan tantangan dari umat Islam dari berbagai penjuru dunia, akhirnya Raja pun mengurungkan niatnya. Hanya saat ini Mekah membebaskan umat Islam dengan madzhab apapun untuk beribadah, dan peninggalan sejarah serta peradaban yang snagat bernilai nilainya pun tidak dihancurkan.
Penolakan Kongres al-Islam di Yogyakarta di kalangan pesantren, komisi keberhasilan Hejaz, dan memiliki organisasi-organiasi kecil di kalangan pesantren kemudian mendorong mereka untuk membentuk organisasi besar yang bisa mewadahi pesantren. Pada tanggal 31 Januari 1926 bertepatan dengan 16 Rajab 1344 H masih dengan semangat bangkit membentuklah organisasi Nahdlatul Ulama (Kebangkitan Ulama) dan memilih KH. Hasyim Asy’ari sebagi Rais Akbar.
NU memang dikenal sebagai organisasi Muslim tradisional dan sejak awal anggotanya adalah laki-laki. Namun demikian, pemimpin NU sejak awal telah menanggapi isu-isu perempuan secara progresif. KH. Wahid Hasyim yang merupakan putera KH. Hasyim Asy’ari misalnya pernah membolehkan perempuan menjadi hakim. Isu perempuan semakin mendapat perhatian tentang Kiai Dahlan semakin berdirinya organisasi perempuan NU di Kongres NU ke XIII di Menes Banten pada tanggal 11-16 Juni 1938. Kongres ini sangat penting karena mulai membicarakan tentang perlunya perempuan mendapatkan hak untuk mendapatkan didikan agama melalui NU. Saat itu, perempuan baru menjadi anggota NU yang hanya bisa menjadi pendengar dan pengikut dan tidak bisa duduk dalam kepengurusan.
Perkembangan penting kembali terjadi pada kongres NU ke XV di Surabaya pada tanggal 5-9 Desember 1940. Ketika itu terjadi, terjadi tanggapan sengit yang diminta agar anggota perempuan NU memiliki struktur pengurusnya sendiri di NU. Kiai Dahlan termasuk mereka yang gigih memperjuangkan agar diterima tersebut diterima. Hingga sehari sebelum kongres berakhir, peserta tidak dapat memutuskan hingga akhirnya memutuskan untuk memutuskan akhirnya pada Pengurus Besar Syuriah NU. Kesempatan ini digunakan oleh Kiai Dahlan untuk mendapatkan izin yang dikeluarkan dari KH. Hasyim Asy’ari dan KH. Wahab Hasbullah. Setelah diperoleh, maka peserta kongres pun dengan mudah menyelesaikan perlunya anggota perempuan NU untuk memiliki struktur kepengurusannya sendiri di dalam NU. Pada Kongres NU ke-XVI di Purwokerto tanggal 29 Maret 1946, struktur kepeng anggota NU disahkan dan diresmikan sebagai bagian dari NU. Namanya kompilasi itu adalah Nahdhlatul Ulama Muslimat yang disingkat NUM. Ketua pertama terpilihnya adalah Ibu Chadidjah Dahlan dari Pasuruan yang tak lain adalah isteri Kiai Dahlan.
Kebangkitan perempuan NU juga kebangkrutan perempuan NU yang dipelopori oleh tiga serangkai, yaitu Murthasiyah (Surabaya), Khuzaimah Mansur (Gresik), dan Aminah (Sidoarjo). Pada Kongres NU ke XV tahun 1940 di Surabaya, juga hadir puteri-puteri NU dari berbagai cabang yang mengadakan rapat sendiri yang menyepakati pembentukannya Puteri Nahdlatul Ulama Muslimat (Puteri NUM). Mereka sebetulnya sudah menyetujui Kongres NU agar disahkan sebagai organisasi yang berdiri sendiri di dalam NU, namun Kongres hanya membahas Puteri NUM sebagai bagian dari NUM. Dalam dua tahun, Puteri NUM meminta agar memiliki Pimpinan Pusatnya sendiri yang dipisahkan dari NUM karena organisasi Puteri NUM di tingkat cabang terus meningkatkan.
Pengurus Besar Nahdlatul Ulama (PBNU) kemudian membentuk Pengurus Pusat Puteri NUM yang diberi nama Dewan Pimpinan Fatayat NU pada tanggal 26 Rabiul Akhir 1939/14 Februari 1950. Selanjutnya Kongres NU ke-XVIII tanggal 20 April-3 Mei 1950 di Jakarta dapat dilakukan mengesahkan Fatayat NU menjadi salah satu badan otonom NU. Namun berdasarkan proses yang berlangsung selama perintisan hingga ditetapkan, FNU menyatakan disetujui di Surabaya pada tanggal 24 April 1950 bertepatan dengan 7 Rajab 1317 H. Pucuk Pimpinan Fatayat NU pertama adalah Nihayah Bakri (Surabaya) sebagai Ketua I dan Aminah Mansur (Sidoarjo) sebagai Ketua II Kepengurusan pada waktu itu hanya memiliki dua bagian, yaitu bagian penerangan danpendidikan.
