Description The informal sector is a significant part of the modern economy. This is particular true in African economies that are characterized by a relatively high degree of activity in this sector. While the share of the informal economy has been going down, it remains relatively high with an average of approximately 40% across the continent. There are several factors that account for the presence of such a large number of firms and workers that are not formally registered by local or central governments. Irrespective of the reasons, the continued presence of a large number of enterprises in the informal economy is a major concern for policy makers given its implications for the productivity of the enterprises, efficacy of government policies and finance, and effects on workers’ welfare. Formal firms are significantly more productive than their informal counterparts. By operating in the informal sector, governments are less able to levy taxes on these enterprises. This is a major concern given the limited tax base of most African countries, which has implications for the adequate financing of infrastructure and other public goods. There is also a general efficiency argument for increasing the percentage of firms with formal status. For instance, making the process formality easier can lead to greater competition in the private sector. This ease of entry leads to lower product prices, greater efficiency, and increased welfare. Employees may also benefit from higher labor standards in the formal sector. This paper assesses the determinants of formality by analyzing a new and original dataset of start-up firms in Ivory Coast, Kenya, Nigeria and Senegal. This unique and original dataset captures information not only on the current registration status of firms but also whether they were registered at start-up. This enables us to determine whether or not firms have changed status either way and for what reasons. Our results show that approximately 5% of firms that registered at start-up later became informal. This effect is significantly associated with the amount of informal payments to government officials by firms to “get things done”. In other words, bribe payments encourage the withdrawal of firms from formal status after registering at start-up. On average, firms use 3% of the annual sales for informal payments or bribes. Our results therefore support one of the key findings in the literature that corruption increases the cost of doing business, and has adverse effects on the likelihood of formality. We also analyzed the determinants of formality in a way that is similar to the approach that is commonly done in the literature by examining firms that use to be informal but are now formal. We found that access to finance, higher education, size at start-up and previous experience of the firm owner in working for a formal firm increase the likelihood of formality. On the other hand, higher bribe payments lower the likelihood of going into formality. Given the size of the informal sector and benefits of formalization, many countries have initiated major reforms to streamline bureaucratic processes. Some countries such as Rwanda have made major strides in this process that is reflected in their rapidly rising investment climate rankings. The government of Mali streamlined its tax payment system to reduce its burden and increase efficiency. Nevertheless, the proportion of informal firms remains significantly high in the sub-Saharan region, and therefore the scope to understanding the contributing factors remains important.