This paper examines the criteria that males and females when choosing their tourism destination and whether such differences result in different destination preferences. Gender is an important variable in shaping consumer behaviour. As Aitchison (2003) posits holiday experience can be evaluated as a process, wherein gender relations are “constructed, legitimated, reproduced and reworked”, gender differences are an important aspect for tourist destination. Given that tourism is an important sector in Malaysia, the study intends to examine the gender differences in tourism destination choices. Based on online survey among 134 males and females young travelers ranging from 20-40 years old, responses were analysed using systematic analysis to understand the gender differences when choosing preferred tourism destination. The study found that gender differences had some influence on tourist preferences and the justifiability of destination decisions. This finding strengthens the theory by Bem (1981) and Spence (1986) that gender is significantly linked to different consumer variables such as leisure activities and preferences including tourism destination choices. As gender has been accepted as a functional factor in tourism especially for market segmentation, it is recommended that marketers as such recognise that there are gender differences in information processing when designing tourism destination marketing campaigns.