Fuel subsidies, which artificially lower consumer prices through government spending, are frequently targeted for removal by economists and international organizations. What accounts for the variable outcomes of attempts to cut fuel subsidies in Latin America? Previous research attributes reform failure to the government’s poor strategic choices. While the government’s decisions are important, they depend on a functioning bureaucratic state apparatus for implementation. This article widens the lens of inquiry, theorizing that the presence of a Weberian bureaucracy creates the institutional preconditions that allow leaders latitude in designing and implementing politically optimal reform strategies, while a politicized and unprofessional bureaucracy limits leaders’ choices, driving politically volatile reforms. Through a pair of case studies, this article demonstrates that, in Brazil and Bolivia, state strength was causally prior to strategic choices in the reform process. In Brazil, the historically strong state was necessary in facilitating a gradual and multi-step reform process that ended in success, while in Bolivia, the deeply politicized state forced the government into adopting a “big-bang” approach that quickly failed after protests. My study shows that leaders in weak states have a narrower array of reform strategy choices available than their strong state counterparts. This finding propounds that the state is a crucial first mover in policy reform, casting doubt on the prospects of reforms that do not first address the deeper problem of state weakness.