This article discusses places and practices of young heterosexual Malaysian Muslims dating in non-private urban spaces. It is based on research conducted in Kuala Lumpur in two consecutive summers 2016 and 2017. Malaysian law (Khalwat law) does not allow for two unrelated people (where at least one of them is Muslim) of opposite sexes to be within ‘suspicious proximity’ of one another in public. This law significantly influences behaviors and activities in urban spaces in KL. In addition to the legal framework, the beliefs of Malaysian Muslims significantly influence the way they perceive space and how they behave in the city. The article discusses the empirical theme, beginning with the participants’ narratives of their engagement with the dominant sexual and gender order in non-private spaces of KL. Utilizing questionnaires, interviews and observations, this article draws upon a qualitative research project and questions the analytical usefulness of the notion of public space (as a Western construct) in the context of an Islamic, post-colonial, tropical, global city.