The perception of organizational legitimacy is influenced by different factors at the micro and macro levels. Organizational approval and support depend on the judgment criteria applied by the involved stakeholders. This research aims to analyze how legitimation criteria affect the different types of organizational legitimacy. Specifically, we analyze how legitimacy perception is influenced by individuals’ gender in an uncertain crisis environment, considering gender and uncertainty as the main variables. Our research was carried out in a global context of uncertainty generated by the COVID-19 pandemic. The results of the study confirm that gender and uncertainty play a relevant role in the legitimacy evaluation process. Men and women use different mindsets when evaluating organizations’ legitimacy. In a context of uncertainty, men's legitimacy evaluation is mainly based on cognitive criteria, while women are moved by pragmatic criteria. The study provides relevant contributions, both theoretical and practical, to legitimacy theory, strategic management, gender studies and marketing and communication fields, providing insights for customizing organizational legitimation strategies taking into consideration the audience's characteristics and environment.