Intuitively, one can expect that migrant workers have smaller social networks in the new destination country and by that smaller probability of finding a job through referrals. However, empirical analysis of the SOEP data from 2002 to 2008 show that 41.21% of migrant workers and 31.79% of native workers found their current job through referrals. Estimation results of the panel probit model with random effects show that 7.26% statistically significant difference of the predicted probabilities of using referrals between migrant and native workers is not explained by the characteristics of the individuals and firms. In order to explain this puzzle, this paper presents a search and matching model with heterogeneous worker groups and several search channels. The firm observes the noisy signal of the productivity, the nationality and the search channel of the worker to form unbiased expectations about the true productivity of the worker. The probabilities to be hired for the two worker groups and different search channels are determined using ex-ante union bargained wage and expectations of the firm. Calibration results of the model show that even when migrant workers have smaller size of the social network, they gain more from recommendations, because their employment chances are initially much lower than employment chances of native workers.