Online labor marketplaces facilitate the efficient matching of employers and workers across geographical boundaries. The exponential growth of this nascent online phenomenon holds important social and economic implications. Despite this importance, limited effort has been devoted to understand whether potential hiring biases exist in online labor platforms and how they affect hiring outcomes. Using a novel proprietary dataset from a leading online labor platform, we investigate the impact of gender-based stereotypes on hiring outcomes. After accounting for endogeneity via a matched sample approach and quasi-experimental technique, we find evidence of a positive hiring bias towards female workers at the aggregate level. Sub-category analyses show that women are preferred in female-dominated occupations, while men are preferred in male-dominated occupations. Interestingly, women also gain an advantage in gender neutral jobs. We find that the observed hiring bias diminishes as employers gain more hiring experience on the platform. Managerial and practical implications are discussed.