The structure of well-ordered atomic layers of underpotentially deposited (UPD) tellurium on Au(110), Au(100) and Au(111) was studied by in-situ scanning tunneling microscopy (STM). A series of largely commensurate structures is observed, with a close correspondence between coverages obtained from the STM images and the cyclic voltammetry assuming complete discharge of Te4+ during adsorption. A linear dependence of the UPD peak current and the peak potential with the square root of the scan rate is observed indicating that the adsorption phase transition is associated with a two-dimensional, instantaneous nucleation process. The same structures are observed in sulfuric acid and perchloric acid supporting electrolyte. The first UPD structure formed on Au(111) corresponds to a pseudohexagonal packing of Te (0.42 ML) (ML = monolayer) in a single domain superlattice structure with missing atom defects. The superlattice cell is (3 root 7 x 3 root 7)R19 degrees with respect to the constituent Te atom hexagonal cell and is consistent with the (12 x 12) structure on Au(111) reported previously. The second UPD structure on Au(111) is a pseudo-morphic (1 x 1). The Te-substrate interaction favors site specific adsorption, and dipolar repulsion within low-coverage layers is responsible for the open packing.