We report the discovery of twin kilohertz quasi-periodic oscillations (QPOs) in the persistent X-ray flux of the new X-ray transient XTE J2123-058. We detected the QPOs in data taken with the proportional counter array on board the Rossi X-Ray, Timing Explorer on 1998 July 14, when the source count rate was at about 50% of its outburst peak level. The frequencies of the QPOs were 853 +/- 4 and 1129 +/- 8 Hz, The peaks had widths of 32(-8)(+11) and 50(-13)(+18)Hz, and the rms amplitudes were 6.1(-0.6)(+0.7) % and 6.5(-0.8)(+0.9) %, respectively. The QPO frequencies increased marginally with count rate, and the amplitudes showed a small increase with photon energy. On the basis of the appearance in the color-color and hardness-intensity diagrams, the low-frequency power spectrum, and the strength of the kHz QPOs, the system can be classified as an atoll source. The source showed five type I X-ray bursts. The distance to the source is estimated to be about 10 (5-15) kpc, which combined with the high Galactic latitude of 36.degrees 2 indicates that the source is a located in the Galactic halo.