The coexistence of species sharing mutual resources is usually thought to be limited by negative processes such as interspecific competition. This is because an overlap in resource use leads to negative fitness consequences, and traits favouring avoidance of potential competitors, for example in habitat selection, are therefore selected for. However, species interactions are acknowledged to vary from negative (competition) to mutualism, although empirical evidence for positive interspecific interactions from natural communities of other than plants and sessile animals is scarce. Here, we experimentally examined the habitat selection and its fitness consequences of a migrant bird, the pied flycatcher (Ficedula hypoleuca), in relation to the presence of competitively superior birds, resident titmice (Parus spp.). Experiments were conducted on two spatial scales: landscape and nest-site scale. We demonstrate that pied flycatchers were attracted to and accrued fitness benefits from the presence of titmice. Flycatchers breeding in tight association with titmice initiated breeding earlier, had larger broods and heavier young than solitarily breeding flycatchers. This paradoxical result indicates that species interactions may switch from negative to positive and that the coexistence of species is not always restricted by negative costs caused by other species.