Data from the 2007 Developmental Idealism survey conducted in Gansu province in China's northwestern borderlands reveal that Muslims of the Hui and Dongxiang ethnicities reported much higher rates of cohabitation experience than the secular majority Han. Based on follow-up qualitative interviews, we found the answer to lie in the interplay between the highly interventionist Chinese state and the robust cultural resilience of local Islamic communities. Using the 2000 census data and the 2010 China Family Panel Studies data, we further show that women in almost all ten Muslim ethnic groups have higher percentages of underage births and premarital births than Han women, both nationally and in the northwest where most Chinese Muslims live. As the once-outlawed behavior of cohabitation became more socially acceptable during the reform and opening-up era, young Muslim Chinese often found themselves in “arranged cohabitations” as de facto marriages formed at younger-than-legal ages.