In many real-world domains, such as bioinformatics (functional genomics), text classification and image annotation, the goal is to predict a complex output. For example, in functional genomics, the goal is to predict the function of a gene, while the set of functions can be organized as tree (FunCat) or graph (GO ontology). In this talk, we present an approach for predicting structured outputs using ensembles of trees. The proposed approach is scalable to large datasets, different types of outputs and it is applicable to wide range of domains. First, we describe the types of structured outputs that we typically encounter, and then we explain the base classifiers - predictive clustering trees (PCTs). Next, we discuss the ensemble methods that we extended (bagging and random forests) to deal with structured outputs and accordingly adapted the voting schemes. Afterwards, we present experimental evaluation of the proposed approach on wide range of real-world domains. At the end, we present an application of the proposed approach in functional genomics and show that our approach is competitive with state-of-the-art approaches.