Personalized recommender systems based on latent factor models are widely used to increase sales in e-commerce. Such systems use the past behavior of users to recommend new items that are likely to be of interest to them. However, latent factor model suffer from sparse user-item interaction in online shopping data: for a large portion of items that do not have sufficient purchase records, their latent factors cannot be estimated accurately. In this paper, we propose a novel approach that automatically discovers the taxonomies from online shopping data and jointly learns a taxonomy-based recommendation system. Out model is non-parametric and can learn the taxonomy structure automatically from the data. Since the taxonomy allows purchase data to be shared between item- s, it effectively improves the accuracy of recommending tail items by sharing strength with the more frequent items. Ex- periments on a large-scale online shopping dataset confirm that our proposed model improves significantly over state-of- the-art latent factor models. Moreover, our model generates high-quality and human readable taxonomies. Finally, us- ing the algorithm-generated taxonomy, our model even out- performs latent factor models based on the human-induced taxonomy, thus alleviating the need for costly manual taxonomy generation.