Cultural intelligence (CQ) is a multidimensional socio-mental construct that allows a person to effectively explore and understand different cultures for the benefit of the entire organization. Therefore, many studies investigate which factors support or hinder CQ development. Our study anticipates that intercultural social contracts, travel experience and knowledge of foreign languages affect CQ. We further explore how these direct relationships are mediated by the variables of self-efficacy in communication. To confirm or reject our hypotheses we used a sample (n = 190) of university students studying at a private Czech university and a public Russian university that is analyzed using the statistical technique PLS-SEM. Our results confirm that intercultural social contacts, the experience of traveling abroad, and knowledge of foreign languages are positively related to CQ, and that self-efficacy partially positively mediates these relations. The study can serve as the base for other research concentrating on the mediators of the factors supporting CQ.