This paper examines the effect of regulatory burdens related to tax administration on firms' compliance costs in Africa. Using cross-country firm-level data, the results show that regulatory burdens related to tax administration significantly increase firms' compliance costs compared to burdens related to other kinds of government regulations. The results further show that firms' relationships with tax officials affect their compliance costs. While firms that are frequently inspected by tax officials have higher compliance costs, firms that are requested to pay bribes by tax officials, on the other hand, have lower compliance costs. These results, which remain robust after accounting for other firm-, sector- and country-specific factors, highlight that regulatory burdens related to taxation play a bigger role in increasing overall compliance costs in Africa than other forms of regulatory burdens, and that firms may look to informal ways to reduce the burden by paying bribes to tax officials.