Agglomeration economies are among the most important factors to increase firm productivity. However, there is little evidence supportive of this in Africa. By applying the conditional and nested logit models, this paper examines the relationship between firm locations and infrastructure accessibility in Rwanda. It is found that agglomeration economies matter to even one of the smallest countries in Africa. It is also found that infrastructure availability has an important role in affecting the firm location decision. Electricity access and transport connectivity to the domestic and international markets are found to be important to attract new investment. In addition, the quality of local labor supplied, measured by educational attainment, is found as an important determinant of firm location, while the effect of labor costs remains inconclusive.