This paper analyzes firm and policy level variables that influence firms’ decisions to locate in the formal and the informal sector. Using a unique and new dataset from four African countries (Cote d’Ivoire, Kenya, Nigeria and Senegal) with detailed information on firms that have transitioned between formal and informal status, we shed further light on the issue on the determinants of formality. We found that firm productivity and corruption (in terms of informal payments made by firms) significantly lead to firms going back into the informal sector even after initially registering at start-up. Higher productivity, having access to bank finance at start-up and education increase the likelihood of switching to formal status after initially being unregistered or informal at start-up. Additionally, we find that time cost (relative to monetary cost) of government regulations reduces the likelihood of firms staying in the formal sector.