Facebook Marketplace is quickly gaining momentum among consumers as a favored customer-to-customer (C2C) product trading platform. The recommendation system behind it helps to significantly improve the user experience. Building the recommendation system for Facebook Marketplace is challenging for two reasons: 1) Scalability: the number of products in Facebook Marketplace is huge. Tens of thousands of products need to be scored and recommended within a couple hundred milliseconds for millions of users every day; 2) Cold start: the life span of the C2C products is very short and the user activities on the products are sparse. Thus it is difficult to accumulate enough product level signals for recommendation and we are facing a significant cold start issue. In this paper, we propose to address both the scalability and the cold-start issue by building a collaborative multi-modal deep learning based retrieval system where the compact embeddings for the users and the products are trained with the multi-modal content information. This system shows significant improvement over the benchmark in online and off-line experiments: In the online experiment, it increases the number of messages initiated by the buyer to the seller by +26.95%; in the off-line experiment, it improves the prediction accuracy by +9.58%.