Urbanisation has created an environment with a broad spectrum of habitats of differing quality for birds. Understanding habitat characteristics is necessary for effective conservation of species in urban environments. We investigated the vegetation requirements of a small, shrub-nesting, Australian bird, the Superb Fairy-wren (Malurus cyaneus), and the relative quality of urban habitats in the Illawarra region of New South Wales. Vegetation was assessed in three different habitats: suburban sites within Superb Fairy-wren territories (n = 20 sites), suburban sites where Fairy-wrens were absent (n = 20), and rural–woodland edge in which Fairy-wrens were present (n = 17). This third habitat represents a habitat assumed to be the best possible habitat for this species within the landscape. We analysed structure and floristics of the vegetation. The three habitats were significantly different from each other both in vegetation structure and floristic composition. While there was some variability in habitat selection in suburban areas, Superb Fairy-wrens were largely restricted to areas that have a dense layer of native shrubs surrounding grassy areas. They were absent from suburban sites where there were either few shrubs in total or sites with exotic shrubs, regardless of abundance. It was predicted that non-suburban habitats (habitat located on the rural–remnant edge) would be of a higher quality than suburban habitats (habitat within residential housing) owing to a prevalence of native vegetation. However, these sites were dominated by a single exotic species, Lantana (Lantana camara). Despite this plant replacing native vegetation, it was an important habitat feature. Either this plant or native shrubs must be available for this species to colonise a site.