This paper presents our work to recommend brands to customers that might be relevant to their style but the brands are new to them. To promote the exploration and discovery of new brands, we leverage article-embeddings, also known as Fashion DNA, a learned en- coding for each article of clothing at Zalando, that is utilized for product and outfit recommendations. The model used in Fashion DNA’s work proposed a Logistic Matrix Factorization approach using sales data to learn customer style preferences. In this work, we evolved that approach to circumvent the cold-start problem for recommending new brands that do not have enough sales or digital footprint. First, we computed an embedding per brand, named Brand DNA, from the Fashion DNA of all articles that belong to a given brand. Then, we trained a model using Logistic Matrix Factorization to predict sales for a set of frequent customers and brands. That allowed us to learn customer style representations that can be leveraged to predict the likelihood of purchasing from a new brand by using its Brand DNA. Customers are also able to further explore Zalando’s assortment moving from the more popular products and brands.