Monolayer tellurium (Te) or tellurene has been suggested by a recent theory as a new two-dimensional (2D) system with great electronic and optoelectronic promises. Here we present an experimental study of epitaxial Te deposited on highly oriented pyrolytic graphite (HOPG) by molecular-beam epitaxy. Scanning tunneling microscopy of ultrathin layers of Te reveals rectangular surface cells with the cell size consistent with the theoretically predicted β-tellurene, whereas for thicker films, the cell size is more consistent with that of the [100] surface of the bulk Te crystal. Scanning tunneling spectroscopy measurements show that the films are semiconductors with the energy band gaps decreasing with increasing film thickness, and the gap narrowing occurs predominantly at the valence-band maximum (VBM). The latter is understood by strong coupling of states at the VBM but a weak coupling at conduction band minimum (CBM) as revealed by density functional theory calculations.