Although considerable discussion has been devoted to the macro determinants of labor market variables across genders, comparatively little attention has been given to the contribution of the informal economy to this market. This study was aimed at empirically investigating the impact of the size of the shadow or informal economy (IE) on labor market variables across genders in 12 Middle Eastern countries. The study used quarterly time series data on each country under investigation, covering 1991 to 2015. Phillips-Perron unit root tests were carried out to verify the stationarity of the examined economic series. An autoregressive distributed lag approach was adopted to conduct cointegration tests and estimate long-run regression coefficients and error correction terms. The results indicated that the IE served men and women differently across countries. Whereas this economy had a long-run positive relationship with men's employment rates in Bahrain, Iran, Qatar, and Turkey, this relationship existed among women only in Israel. IE activities matter in the employment of men and women in Middle Eastern countries. The sizes of IEs in the labor market are a significant factor that favors men's employment rather than that of women.