The dominant criterion to determine when an introduced species is established relies on the maintenance of a self-sustaining population in the area of introduction, i.e. on the viability of the population from a demographic perspective. There is however a paucity of demographic studies on introduced species, and establishment success is thus generally determined by expert opinion without undertaking population viability analyses (PVAs). By means of an intensive five year capture-recapture monitoring program (involving >12,000 marked individuals) we studied the demography of five introduced passerine bird species in southern Spain which are established and have undergone a fast expansion over the last decades. We obtained useful estimates of demographic parameters (survival and reproduction) for one colonial species (Ploceus melanocephalus), confirming the long-term viability of its local population through PVAs. However, extremely low recapture rates prevented the estimation of survival parameters and population growth rates for widely distributed species with low local densities (Estrilda troglodytes and Amandava amandava) but also for highly abundant yet non-colonial species (Estrilda astrild and Euplectes afer). Therefore, determining the establishment success of introduced passerine species by demographic criteria alone may often be troublesome even when devoting much effort to field-work. Alternative quantitative methodologies such as the analysis of spatio-temporal species distributions complemented with expert opinion deserve thus their role in the assessment of establishment success of introduced species when estimates of demographic parameters are difficult to obtain, as is generally the case for non-colonial, highly mobile passerines.