Observationally equivalent workers are paid higher wages in larger firms. This fact is often named as the "firm-size wage gap" and is regarded as a key empirical puzzle. Using micro-level data from Turkey, we document a new stylized fact: the firm-size wage gap is more pronounced for informal (unregistered) jobs than for formal (registered) jobs. To explain this fact, we develop a two-stage wage-posting game with market imperfections and segmented markets, the solution to which produces wages as a function of firm size in a well-defined subgame-perfect equilibrium. The model proposes two explanations. First, taxes on formal employment generate a wedge between formal and informal size wage gaps. Thus, government policy can potentially affect the magnitude of the firm-size wage gaps. The second explanation features a market-based framework with strategic interactions. Relative to small firms, large firms typically post higher wages for both formal and informal jobs they open. A high-wage formal job attracts a larger pool of applicants than a high-wage informal job. The larger pool of applicants for the formal job, in turn, allows the firm to somewhat lower the initial wage offer, while this second-round effect is negligible for informal jobs. As a result, size differentials are lower in formal jobs than informal jobs. We argue that the observed patterns in the use of social connections in job search and heterogeneity in job preferences can be used to justify the validity of this second mechanism.