Cultural Intelligence (CI) refers to the motivation and ability to understand and deal with cultural differences. As such, it is assumed to play a role in the effectiveness of social contact and communication between people from different cultures. Given its relevance to international relations, it is imperative to test which individual and group factors are associated with CI. Therefore, in the present study we examine cross-cultural and gender differences in CI. In one of their classes at their university, students (N = 829) from Egypt and Saudi Arabia completed a multidimensional measure of CI. The results showed an interesting pattern of interactions between country and gender, which indicated that Egyptian men did not significantly differ from co-national women, but Saudi men scored significantly lower than women. We suggest that the different patterns of results in the two countries may partly arise from different levels of exposure to different cultures and partly from subtle differences in the constitution of the samples. Knowledge of individual and group differences in cultural intelligence may potentially contribute to explaining differential levels of success in individuals or countries in dealing with cultural differences.