The Galactic Archaeology with HERMES (GALAH) survey is a large high-resolution spectroscopic survey using the newly commissioned High Efficiency and Resolution Multi-Element Spectrograph (HERMES) on the Anglo-Australian Telescope. The HERMES spectrograph provides high-resolution (R ~ 28 000) spectra in four passbands for 392 stars simultaneously over a 2 deg field of view. The goal of the survey is to unravel the formation and evolutionary history of the Milky Way, using fossil remnants of ancient star formation events which have been disrupted and are now dispersed throughout the Galaxy. Chemical tagging seeks to identify such dispersed remnants solely from their common and unique chemical signatures; these groups are unidentifiable from their spatial, photometric or kinematic properties. To carry out chemical tagging, the GALAH survey will acquire spectra for a million stars down to V ~ 14. The HERMES spectra of FGK stars contain absorption lines from 29 elements including light proton-capture elements, α-elements, odd-Z elements, iron-peak elements and n-capture elements from the light and heavy s-process and the r-process. This paper describes the motivation and planned execution of the GALAH survey, and presents some results on the first-light performance of HERMES.