Declines in population size can compromise the viability of populations by reducing the effective population size (Ne), which may result in loss of genetic diversity and inbreeding. Temporal population genetic data can be a powerful tool for testing the presence and severity of reductions in Ne. The Gouldian finch (Erythrura gouldiae) is a flagship for conservation of Australian monsoonal savanna species. This species underwent severe population declines in the twentieth century due to land use changes associated with European colonization. Microsatellite and mitochondrial genetic data from Gouldian finch samples sourced from natural history collections prior to land use changes were compared with contemporary samples to estimate the severity of decline in effective population size and to detect changes in gene flow. These data show that Gouldian finch decline was not as severe as some sources suggest, and that population genetic connectivity has not changed following land use changes in the twentieth century. Multiple estimators of current Ne using genetic data from consecutive years suggest the Gouldian finch Ne is likely between a few hundred and a few thousand individuals, with some estimates within the range considered of conservation concern. This work has identified the need to genetically characterize populations in Queensland, and to understand critical demographic parameters (e.g. lifespan) in the Gouldian finch. Understanding these factors is vital to further improve genetic estimates of population size, key to the formation of appropriate conservation management of this species.