Species persistence and maintenance of genetic diversity are strongly affected by dispersal and historical distribution, especially when species depend on habitat that is non-uniform or fluctuates dramatically with changing climate. Australo-Papuan rainforest has fluctuated dramatically since the last glacial maximum (around 20 kya). To understand how prehistoric climate fluctuation affected population connectivity and genetic diversity in a rainforest edge species, we screened 27 Palm Cockatoo samples from Cape York Peninsula (Australia) and southern Papua New Guinea (PNG) in 1132 single nucleotide polymorphisms in 342 nuclear loci and the mitochondrial ND2 gene. We also modelled the birds' distribution at present, mid-Holocene (similar to 6 kya) and the last glacial maximum (similar to 21 kya). Population differentiation in nuclear genomic data among Australian populations aligns with distribution contraction to mountainous refugia at the mid-Holocene (similar to 6 kya). Lack of nuclear divergence between PNG and Australia may reflect late-Holocene recolonisation, but different ND2 haplotypes suggest early stages of divergence. Although admixed individuals suggest some gene flow, recent movement restriction to/from Australian refugia is suggested by a unique ND2 haplotype, genomic divergence and a vocal dialect boundary shown previously. Our results show how prehistoric climate fluctuation affects present-day and future species conservation in dynamic rainforest edge ecosystems.