We propose a random network model incorporating heterogeneity of agents and a continuous notion of homophily. Unlike the vast majority of the corresponding economic literature, we capture homophily in terms of similarity rather than equality of agents. We show that if links between similar agents are indeed more likely, our homophilous random network model exhibits clustering. Moreover, simulations indicate that the well-known small-world phenomenon is preserved even at high homophily levels. As a possible application we provide a stylized labor market model, where a firm can hire a worker via the social network.