We used scanning tunneling microscopy (STM) to investigate high-coverage structures of atomic oxygen that develop on Pt(111) under ultrahigh vacuum (UHV) conditions. We find that oxygen atoms arrange into a p(2×1) structure that grows in three rotationally degenerate domains as the oxygen coverage increases above 0.25ML (monolayers). STM also shows that atomic-scale protrusions and chains, with apparent heights of 1.7Å, begin to develop within the p(2×1) domains once the coverage reaches about 0.40ML at 450K. We attribute these features to a Pt oxide chain compound that forms as oxygen atoms adsorb between the close-packed oxygen rows of the surrounding p(2×1) structure. As the coverage increases to 0.75ML, the chains form an interconnected network of Y-shaped structures with regions locally resembling a honeycomb. Each branch of the Y-structure consists of two to three side-by-side Pt oxide chains about 19–24Å in length. We suggest that uniaxial strain causes the chains to select specific lengths that are commensurate along the close-packed directions of the Pt(111) substrate, and that stress relief governs the chain branching and formation of the interconnected network. These results demonstrate that Pt oxide chain formation occurs during the early stages of Pt(111) oxidation, and that long-range effects determine the structural characteristics of the resulting chain network. These findings may have important implications for understanding the oxidation and reactivity of Pt surfaces under oxidizing conditions.