Using enterprise data for the economies of Central and Eastern Europe and the CIS, this study examines the effects of corruption on productivity. Corruption is defined as a “bribe tax” and is compared to another form of institutional inefficiency, which is often believed to be closely linked with corruption: the “time tax” imposed on firms by red tape. When testing their effects in the full sample, only the bribe tax appears to have a negative effect on firm-level productivity, while the effect of the time tax is insignificant. At the same time, there is no evidence of a trade-off between the time and the bribe taxes, implying that bribing does not emerge as a second-best option to achieve higher productivity by helping circumvent cumbersome bureaucratic requirements. When the sample is split between EU and non-EU countries, the time tax turns out to have a negative effect only in EU countries and the bribe tax only in non-EU countries. This suggests that the institutional environment influences the way in which firm behaviour affects firm performance. In particular, the impact of bribing for individual firms appears to vary depending on overall institutional quality: in countries where corruption is more prevalent and the legal framework is weaker, bribery is more harmful for firm-level productivity.