Cultural tourism is one of the most sustainable and fastest-growing types of tourism, and so has been widely studied. Despite countless works analyzing the possible factors that can condition the choice of the tourist destination, few have addressed how they may differ by sex and within cultural tourism, and they contradict. This paper analyzes this phenomenon through the dimensions of cultural offerings, services and motivations in the city of Málaga, a very tourist city in Spain, which is the fourth country out of 167 with the most world heritage sites—UNESCO. Partial least squares—structural equation modelling (PLS-SEM) and importance-performance map analysis (IPMA) were performed for a database of 415 cultural tourists survey responses. The results showed differences between constructs depending on the sex of the tourists. For men, the factor that most affects the choice of destination is tourist motivation—namely, the reason for their visit— followed by services. Conversely, services are first for women, followed by cultural offerings and motivations. The results of this study can be valuable when designing more specific tourism strategies adapted to the profile of tourists.