The focus of this article is on the Salafiyya-Madkhaliyya in Indonesia, which takes its name from Saudi scholar Rabi al-Madkhali. After an account of how they emerged and developed in Indonesia, the relationship of the Madkhalis with the state, which is based on a "fiqh of obedience", is analyzed. It is argued that, while this legal underpinning necessitates that they give total loyalty to the ruler (wali l-amr, or ulu l-anzr), the Indonesian Madkhalis are unable to entirely follow this principle. The Madkhalis have had to come to terms with the fact that Indonesia follows a democratic system, which, in fact, prevents the comprehensive accommodation of their Salad principles. The resulting ambiguities prove difficult to solve. It is argued here that the negotiation between Madkhali Salans and the Indonesian state is characterized by the constant efforts of the former to tackle those ambiguities.