Real-world objects can often be decomposed into a set of parts, where a specific relational structure of parts determines the object label. This thesis presents a novel Structured Output Learning approach, combining a graph-based and a probabilistic model representation. It learns from examples with varying numbers of attributed parts and relations, and assigns likelihoods to the existence of object structures. Different applications for learnt models are introduced, with a focus on classification of object structures, and recognition of object structures in a set of cluttered objects. The proposed model representation and learning are data-independent, and can be applied to many different kinds of domains. Experimental evaluation in the domains of high-level image understanding, classification of toxic molecules, natural language processing and behaviour model learning is presented.