Mobile social networking becomes increasingly popular with the explosive growth of mobile devices. By allowing mobile users to interact with potential friends around the real world, it enables new social interactions as a complement to web-based online social networks. In this paper, we introduce a secure friend discovery mechanism based on encounter history in mobile social networks. By exploring the fact that sharing encounters indicate common activities and interests, our scheme can help people make friends with like-minded strangers nearby. We provide peer-to-peer confidential communications with the location privacy and encounter privacy being strictly preserved. Unlike most existing works that either rely on a trusted centralized server or existing social relationships, our algorithm is designed in an ad-hoc model with no such limitation. As a result, our design is more suitable and more general for mobile social scenarios. Extensive theoretical analysis and experimental study are conducted, and the results indicate that our scheme is feasible and effective for privacy-preserving friend discovery in mobile social networks.