Understanding how pathogens invade and become established in novel host populations is central to the ecology and evolution of infectious disease. Influenza viruses provide unique opportunities to study these processes in nature because of their rapid evolution, extensive surveillance, large data sets and propensity to jump species boundaries. H5N1 highly pathogenic avian influenza virus (HPAIV) is a major animal pathogen and public health threat. The virus is of particular importance in Indonesia, causing severe outbreaks among poultry and sporadic human infections since 2003. However, little is known about how H5N1 HPAIV emerged and established in Indonesia. To address these questions, we analysed Indonesian H5N1 HPAIV gene sequences isolated during 2003-2007. We find that the virus originated from a single introduction into East Java between November 2002 and October 2003. This invasion was characterized by an initially rapid burst of viral genetic diversity followed by a steady rate of lineage replacement and the maintenance of genetic diversity. Several antigenic sites in the haemagglutinin gene were subject to positive selection during the early phase, suggesting that host-immune-driven selection played a role in host adaptation and expansion. Phylogeographic analyses show that after the initial invasion of H5N1, genetic variants moved both eastwards and westwards across Java, possibly involving long-distance transportation by humans. The phylodynamics we uncover share similarities with other recently studied viral invasions, thereby shedding light on the ecological and evolutionary processes that determine disease emergence in a new geographical region.