The AFU was formed by the Egyptian Feminist Union (EFU) under Huda Sharawi. The EFU was the starting point of the organized feminist movement in the Arab World when it was founded in 1923. Becoming a member of the International Women Suffrage Alliance and Women’s International League for Peace and Freedom, it wished to organise the women's movement of the Arab world internationally, in the same manner as the women's movement in the West.
In 1938, the EFU organised the Eastern Women’s Conference for the Defense of Palestine in Cairo, and Huda Sharawi suggested the individual countries establish feminist unions, and that those unions formed an umbrella organization, spanning the Arab world. The AFU were originally mainly an offspring of the Arab Women's Association of Palestine, which had attended the Conference.
On 7 December 1944, the EFU convened the Arab Feminist Congress or Arab Women's Congress of 1944 in Cairo, which formally established the AFU. The AFU was based in Egypt and administered by the EFU: Sharawi became the AFU’s first president and its treasurer and secretary were also Egyptians. Trans-Jordan, Iraq, Syria, Palestine, and Lebanon was given two representatives each on the board.
From the 1960s, several totalitarian regimes in newly independent Arab countries opposed feminist organizing. In 1956, the Egyptian government forced the closure of the EFU. The AFU transferred its headquarters to Beirut, but the organization diminished.