Disease spreading is a topical issue in a variety of fields ranging from computer viruses in the Internet to air-borne (e.g. influenza) diseases in societies. In particular, the description of the spread of sexually transmitted diseases (Chlamydia, Syphilis, Gonorrhea, AIDS) across population constitutes a major concern for scientists and health agencies. In this context, both data collection on sexual contact networks and the modeling of disease spreading are intensively contributing to the search for effective immunization policies. Here, the spread of sexually transmitted diseases on bipartite scale-free graphs, representing heterosexual contact networks, is considered. We analytically derive the expression for the epidemic threshold and its dependence with the system size in finite populations. The results indicate that in finite bipartite populations with degree distribution as those found in national surveys of sexual attitudes, the onset of the epidemic outbreak takes place for larger spreading rates than in the case in which the bipartite nature of the network is not taken into account. Moreover, the difference between the epidemic thresholds in bipartite and unipartite scale-free networks increases with the system size. Results from numerical simulations for both representations of sexual contacts networks are also presented, confirming the validity of the theoretical results. The approach adopted here indicates that the restriction to crossed infections between the two classes of individuals (males and females) strongly modifies the results previously found for unipartite heterogeneous populations. This has to be taken into account in the design of efficient immunization strategies for sexually transmitted diseases.