‘Muslim’ has become a frequently applied category in immigrant integration policy. While there is extensive research on the construction of this religious category to identify the target groups of these policies, there are few empirical studies on the category use. Many scholars argue that populations of immigrants were increasingly labelled as ‘Muslim’ following the 9/11 terror attacks. Also, the increased application of ‘Muslim’ is debated as the result of the anti-Islam mobilisation by populist right-wing parties or in relation to the institutional accommodation of Islam. This article asks when, through which actors and in which contexts the category ‘Muslim’ entered and evolved in the policy field. The study focuses on parliamentary immigrant integration debates in Austria, Germany and Switzerland (1993–2013). The analysis shows that right-wing parties make use of the category ‘Muslim’ in relation to security and common values. Left-wing actors take up the category to criticise this usage, while mainstream parties do so when discussing the accommodation of Islam. Instances of religious violence were not found to generate a sustained increase in category use, while the agenda setting of populist parties on the right and the extent to which the accommodation of Islam is debated proved to be decisive.