In this study, we investigate the relationship between the informal sector and productivity in West-Africa, using firm-level data collected on 900 formal and informal businesses in the capital cities of Benin, Burkina Faso and Senegal. In our sample design, we have avoided the narrow definition of informality as small scale individual or household firms, and thus included large informal firms. Our results confirm the heterogeneity of the informal sector and the significance of large informal businesses in West Africa. Specifically, they confirm the importance of distinguishing the latter from the small informal firms in describing behavior and identifying obstacles in the investment climate. The productivity gap between formal and informal firms is found to be important for small informal businesses but much less so for large informal ones. The factors shown to be associated with this gap include a number of state failures to provide public services and enforce regulations more systematically.