The wave Of privatization in the 1980s and 1990s increased productivity of many previously state owned enterprises (SOEs). However, governments often do not have sufficient support to privatize SOEs. We provide evidence that threatening privatization and market competition (entry of new firms) can increase the productivity of SOEs, even though privatization and entry of new firms does not occur. We study productivity at Brazil's state-owned oil company Petrobras. Petrobras's total factor productivity increased sharply after it lost its legal monopoly, doubling in 6 years. These large gains occurred despite the fact that Petrobras faced no immediate de facto competition. The threat of competition and privatization was sufficient to generate large productivity gains. These findings suggest that changing the competitive environment can be a powerful force for improving productivity at state-owned firms. Published by Elsevier Ltd.