Understanding the factors that influence food selection and dietary behavior is fundamental to support the successful translation of dietary goals into consumer behavior. The present study aims to identify gender differences in fast food consumers’ reasons for actual fast food meal selection and their purchase intentions. Based on this background, possible opportunities toward implementing healthier and more sustainable fast food options are discussed. Data were collected at three fast food restaurants from different parts of Denmark among randomly selected customers (aged 15 or above). The customers were approached after having ordered their meal. They filled out a questionnaire on reasons for their actual fast food meal selection and purchase intentions in relation to four hypothesized burger menus, including a regular beef burger menu, a wholegrain beef burger menu, a nutrition labeled beef burger menu and a nutrition labeled chicken burger menu. Results showed that the majority of the fast food customers expressed a wish for healthier menus (55% males vs. 64% females agree or strongly agree, p < 0.001) and more sustainable menus in terms of environmental impact (43% males vs. 52% females agree or strongly agree, p < 0.001), however only 7% of the participants’ meals included healthier food choices (n = 740). Habits, taste and price were the main drivers among both genders for the actual meal selection. Compared with women, more men expressed that actual food choice was based on offers and promotions (p < 0.001), and on food perceived as the most satiating (p = 0.001). With regard to purchase intentions, the majority of men preferred a beef burger menu (healthier or regular) over a healthier chicken burger menu or a wholegrain burger menu, whereas the majority of women responded positively to either of the healthier-labeled burger menus (p < 0.001). In conclusion, the study shows that having a focus on gender differences is of particular importance in order to improve the food nutrition environment and support healthier food selections among fast food customers.