The structures of O atoms adsorbed on a metal surface influence the metal properties significantly. Thus, studying O chemisorption on a Zr surface is of great interest. We investigated O adsorption on a Zr(0001) surface using our newly developed structure-searching method combined with first-principles calculations. A novel structural prototype with a unique combination of surface face-centered cubic (SFCC) and surface hexagonal close-packed (SHCP) O adsorption sites was predicted using a single-layer adsorption model (SLAM) for a 0.5 and 1.0 monolayer (ML) O coverage. First -principles calculations based on the SLAM revealed that the new predicted structures are energetically favorable compared with the wellknown SFCC structures for a low O coverage (0.5 and 1.0 ML). Furthermore, on basis of our predicted SFCC + SHCP structures, a new structure within multi-layer adsorption model (MLAM) was proposed to be more stable at the O coverage of 1.0 ML, in which adsorbed O atoms occupy the SFCC+SHCP sites and the substitutional octahedral sites. The calculated work functions indicate that the SFCC + SHCP configuration has the lowest work function of all known structures at an O coverage of 0.5 ML within the SLAM, which agrees with the experimental trend of work function with variation in 0 coverage. (C) 2016 Elsevier B.V. All rights reserved.