A transition toward a sustainable way of living is more pressing than ever. One link to achieving this transition is to increase the currently low level of sustainable consumption, and sustainability labeling has been shown to directly influence sustainable purchasing decisions. E-commerce retailers have recently picked up on a means to inform online shoppers about sustainable alternatives by introducing on their websites third-party and private sustainability labels as nudging instruments. However, despite its increasing relevance in practice, research lacks evidence about the availability and credibility of sustainability labeling in online retail. Our study is guided by the question of how online retailers use sustainability labels to communicate information on the sustainability of products to consumers. Our empirical research is based on a large-scale dataset containing sustainability information of nearly 17,000 fashion products of the leading online retailers in Germany Zalando and Otto. The results show that a large number of fashion products are tagged as sustainable, with two-thirds carrying a private label and one-third a third-party verified label. Only 14% of the tagged products, however, present credible third-party verified sustainability labels. This low percentage makes it challenging for consumers to comprehend to what degree a product is sustainable. The wide distribution of private labels indicates that most of the available sustainability information in the selected online shops addresses only single sustainability issues, preventing comparability. Furthermore, label heterogeneity can add to the confusion and uncertainty among consumers. Our practical recommendations support political initiatives that tackle the risk of greenwashing resulting from uncertified and weak sustainability information.