Background: By September 2, 2021, over 30,000 COVID-19-vaccinated females had reported menstrual changes to the MHRA's Yellow Card surveillance system. As a result, the National Institutes of Health (NIH) is urging researchers to investigate the COVID-19 vaccine's effects on menstruation. Therefore, this study was conducted to explore the menstrual changes after COVID-19 vaccination and/or SARS-CoV-2 infection and their interrelations with demographic, mood, and lifestyle factors in Arab women of childbearing age (CBA). Methodology: A cross-sectional study was conducted during October 2021 using an Arabic-validated and self-administrated questionnaire. In total, 1,254 women of CBA in the Arabic population (15–50 y) with regular menstrual cycles were randomly selected from five countries (Saudi Arabia, Egypt, Syria, Libya, and Sudan). Results: The mean (SD) age of the 1,254 studied females was 29.6 (8.5) years old. In total, 634 (50%) were married, 1,104 (88.0%) had a university education or above, 1,064 (84.4%) lived in urban areas, and 573 (45.7%) had normal body weight. Moreover, 524 (41.8%) were COVID-19 cases, and 98 women (18.7%) reported menstrual changes (MCs). The 1,044 (83.5%) vaccinated females reported 418 (38.5%) MCs after being vaccinated, and these MCs resolved in 194 women (55.1%) after more than 9 months. Statistically significant relationships were observed between the reported MCs and the following variables: age, marital status, level of education, nationality, residence, and BMI. MCs were reported at 293(80.6) after the 2nd dose and were mainly reported after 482 (46.1) Pfizer, 254 (24.3) Astrazenica, and 92 (8.8) Senopharm. Conclusion: MCs among women of CBA after COVID-19 infection and vaccination are prevalent and complex problems and had many determinates.