Abstract The policing of illicit sex formed a key mode of social control in early modern Europe, where reproduction in legally sanctioned marriage was the primary means through which property and status was passed. When Europeans formed overseas colonial settlements sustained by slave labor and populated by people of a broad variety of ethnic and religious backgrounds, this concern with sexually transgressive behavior took on new dimensions. This article takes the case of Dutch trade-company-led colonialism in the seventeenth and eighteenth centuries to examine how colonial visions of social order in Asia, Africa, and the Caribbean shaped authorities’ responses to different types of non-marital sex. To facilitate comparison, these acts are read through narratives of criminalization, comprised of both conceptualizations of crime and prosecution practices. Through an analysis of legislation issued across the Dutch empire, most notably bylaws, combined with a selection of case studies from the juridical practice, we show that a concern with keeping different ethnic, religious, and status groups separate and maintaining European dominance shaped the policing of sexuality in such a way that the distinction between relatively benign sexual “improprieties” and a more serious criminal narrative of sexual “betrayal” was re-arranged along gendered and racialized lines. Conceptualizations and prosecutions alike show a considerably more stringent treatment of sex between non-Christian or non-white men and women of European status than between European men and enslaved or free local women, even when the latter scenario was coercive or violent.