Landscape context can affect how individuals perceive patch quality during colonisation. However, although context-dependent colonisation has been observed in aquatic environments it has rarely been studied in terrestrial environments or at large spatial scales. Here, we assessed how landscape context influenced colonisation rates in a large-scale (c.7000 km2) terrestrial system where colonisers (Willow Warbler Phylloscopus trochilus) are capable of rapid, long-distance movements. Bioacoustic recorders were used to detect first song dates (an indicator of colonisation or re-colonisation) and settlement in 23 naturally replicated habitat patches. We compared support for three competing hypotheses describing colonisation patterns that depend on landscape context (‘redirection’, ‘landscape-selection’ and ‘relative patch size’) with two patch-level hypotheses (patch ‘quality’ and ‘heterospecific attraction’). First song was earlier when habitat availability in the landscape was low, supporting the ‘redirection’ hypothesis. Settlement probability was best predicted by patch ‘quality’ and was lower in woodlands with a dense understorey. Results suggest that colonisation of habitat patches by male P. trochilus after spring migration is spatially hierarchical. First, initial colonisation depends on landscape context, and settlement is then determined by fine-scale vegetation characteristics. More broadly, we suggest that patterns observed in fragmented aquatic environments (e.g. ‘redirection’) can, in some circumstances, be extended to large-scale terrestrial environments.