In this study, we propose a novel methodology for automated detection of buildings from single very-high-resolution (VHR) multispectral images. The methodology uses the principal evidence of buildings: the shadows that they cast. We model the directional spatial relationship between buildings and their shadows using a recently proposed probabilistic landscape approach. An effective shadow post-processing step is developed to focus on landscapes that belong to building regions. The building regions are detected using an original two-level graph theory approach. In the first level, each shadow region is addressed separately, and building regions are identified via iterative graph cuts designed in two-label partitioning. The final building regions are characterised in a second level in which the previously labelled building regions are subjected to a single-step multi-label graph optimisation performed over the entire image domain. Numerical assessments performed on 16 VHR GeoEye-1 images demonstrate that the proposed approach is highly robust and reliable. A distinctive specialty of the proposed approach is its applicability to buildings with diverse characteristics as well as to VHR images with significantly different illumination properties. (C) 2013 International Society for Photogrammetry and Remote Sensing, Inc. (ISPRS) Published by Elsevier B.V. All rights reserved.