Berdirinya Fatayat NU tidak bisa dilepaskan dari sejarah berdirinya Nahdlatul Ulama (NU) sebagai organisasi induknya, dan sejarah Indonesia sebagai tanah airnya. Penjajahan selama bertahun-tahun telah menyebabkan bangsa Indonesia terpuruk. Perjuangan melawan keterbelakangan, kemiskinan, kebodohan, dan keterpurukan akibat penjajahan ini kemudian mengkristal dan melahirkan semangat kebangkitan di seantero negeri hingga mencapai puncaknya pada tahun 1908 yang dikenal sebagai tahun Kebangkitan Nasional. Kalangan pesantren merespon spirit ini dengan membentuk berbagai organisasi pergerakan, 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 pendidikan sosial politik, Nahdlatut Tujjar (Kebangkitan Kaum Saudagar) yang dijadikan basis untuk memperbaiki perekonomian rakyat.
Sementara itu, di Saudi Arabia terjadi perkembangan cukup penting di mana Raja Ibnu Saud ingin menjadikan Madzhab Wahabi di Mekah sebagai asas tunggal dan karenanya ingin menghancurkan semua peninggalan sejarah Islam maupun Pra-Islam yang selama ini kerap diziarahi karena dianggap bid’ah. Perkembangan ini disambut baik oleh kelompok modernis di Indonesia, baik oleh kalangan Muhammadiyah pimpinan oleh Ahmad Dahlan, maupun oleh PSII (Partai Sarekat Islam Indonesia) pimpinan H.O.S. Cokroaminoto. Sebaliknya kalangan pesantren menolaknya.
Perbedaan sikap ini menyebabkan kalangan pesantren dikeluarkan dari 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. Hingga saat ini Mekah membebaskan umat Islam dengan madzhab apapun untuk beribadah, dan peninggalan sejarah serta peradaban yang snagat berharga nilainya pun tidak jadi dihancurkan.
Penolakan Kongres al-Islam di Yogyakarta pada kalangan pesantren, keberhasilan misi Komite Hejaz, dan telah adanya organisasi-organiasi kecil di kalangan pesantren kemudian mendorong mereka untuk membentuk organisasi besar yang bisa mewadahi seluruh kalangan pesantren. Pada tanggal 31 Januari 1926 bertepatan dengan 16 Rajab 1344 H masih dengan semangat kebangkitan dibentuklah 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 merespon isu-isu perempuan secara progresif. KH. Wahid Hasyim yang merupakan putera KH. Hasyim Asy’ari misalnya pernah membolehkan perempuan menjadi seorang hakim. Isu perempuan semakin mendapatkan perhatian ketika Kiai Dahlan mengusulkan 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 kesamaan hak untuk mendapatkan didikan agama melalui NU. Ketika itu kongres baru menyetujui perempuan untuk menjadi anggota NU yang hanya bisa menjadi pendengar dan pengikut dan tidak boleh duduk dalam kepengurusan.
Perkembangan penting kembali terjadi pada kongres NU ke XV di Surabaya pada tanggal 5-9 Desember 1940. Ketika itu, terjadi perdebatan sengit merespon usulan agar anggota perempuan NU mempunyai struktur pengurusnya sendiri di dalam NU. Kiai Dahlan termasuk mereka yang gigih memperjuangkan agar usulan tersebut diterima. Hingga sehari sebelum kongres berakhir, peserta tidak mampu memutuskan hingga akhirnya disepakati untuk menyerahkan keputusan akhirnya pada Pengurus Besar Syuriah NU. Kesempatan ini dimanfaatkan oleh Kiai Dahlan untuk mendapatkan persetujuan secara tertulis dari KH. Hasyim Asy’ari dan KH. Wahab Hasbullah. Setelah didapatkan, maka peserta kongres pun dengan mudah menyetujui perlunya anggota perempuan NU untuk memiliki struktur kepengurusannya sendiri di dalam NU. Pada Kongres NU ke-XVI di Purwokerto tanggal 29 Maret 1946, struktur kepengurusan anggota perempuan NU disahkan dan diresmikan sebagai bagian dari NU. Namanya ketika 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 membakar semangat kalangan perempuan muda 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 pertemuan sendiri yang menyepakati dibentuknya Puteri Nahdlatul Ulama Muslimat (Puteri NUM). Mereka sebetulnya sudah mengajukan kepada Kongres NU agar disahkan sebagai organisasi yang berdiri sendiri di dalam NU, namun Kongres hanya menyetujui Puteri NUM sebagai bagian dari NUM. Dalam dua tahun, Puteri NUM meminta agar mempunyai Pimpinan Pusatnya sendiri yang terpisah dari NUM karena organisasi Puteri NUM di tingkat Cabang terus bertambah.
Pengurus Besar Nahdlatul Ulama (PBNU) kemudian menyetujui pembentukan 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 secara resmi mengesahkan Fatayat NU menjadi salah satu badan otonom NU. Namun berdasarkan proses yang berlangsung selama perintisan hingga ditetapkan, FNU menyatakan dirinya didirikan 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 mempunyai dua bagian, yaitu bagian penerangan danpendidikan.