This paper describes the electrochemical formation of tellurium atomic layers on Au(100) and the phase transitions associated with those layers. Voltammetry in HTeO2+ shows two clear sub-monolayer reduction features prior to the onset of bulk Te deposition. In situ electrochemical scanning tunneling microscopy (STM) has shown that a 0.25 coverage (2 x 2) structure is the first Te adlayer formed by scanning into the first reduction feature. The (2 x 2) unit cell was also observed using low energy electron diffraction (LEED). As the potential was shifted through the first deposition feature, the (2 x 2) converted to a 0.33 coverage (2 x root 10) structure, by the random introduction of Te atom chains in the initial (2 x 2) layer. Te-Te distances in the chains were consistent with Te atoms at their van der Waals diameter, 0.44 nm. The chains can be thought of as boundaries between domains of the (2 x 2), shifted by root 2 from each other. The (2 x root 10) structure consists of a complete layer of these chains. Further deposition, past the first reduction feature, resulted in a 0.375 coverage (2 x 4) structure. The (2 x 4) also appears to consist of chains of Te atoms, but with every third atom set in a lower site where they are not easily imaged under some tunneling conditions. Scanning into the second reduction feature, a shoulder on bulk Te deposition, atoms in the (2 x 4) structure became compressed, converting to a structure with a coverage of 0.67 and a (root 2 x root 5) unit cell. At this stage, the Te atoms were no longer separated by a distance consistent with their van der Waals diameter, but with one closer to that of the underlying Au atoms, 0.288 nm. The Te atoms appear to have covalently bonded to each other, simultaneously inducing a roughening transition in the surface. The transition may result from stress induced via bonding between the Au substrate and this covalently bound Te atomic layer. All the structures described above are single atomic layers. Three-dimensional nucleation progressed at potentials associated with the bulk Te deposition feature. Needles, or rectangular Te atom domains with high aspect ratios, propagating in the [100], were formed in a second layer, apparently on domains of the (root 2 x root 5) structure.