We have measured the time-of-flight of ortho-positronium emitted from Cs-, Na- and Li-coated single-crystal tungsten surfaces. The data obtained after the coating show a new positronium energy component with a specific energy loss in addition to the component whose emission energy is simply determined by the positron and the electron work functions. We suggest that this new component is attributed to the formation of positronium accompanied by inter-band transition and/or surface plasmon excitation at the surfaces.