During observations with the Rossi X-Ray Timing Explorer from 1997 June 31 to July 3 we discovered two simultaneous kHz quasi-periodic oscillations (QPOs) near 500 and 860 Hz in the low-mass X-ray binary and Z source Cygnus X-2. In the X-ray color-color diagram and hardness intensity diagram (HID), a clear Z track was traced out, which shifted in the HID within 1 day to higher count rates at the end of the observation. Z track shifts are well known to occur in Cyg X-2; our observation for the first time catches the source in the act. A single kHz QPO peak was detected at the left end of the horizontal branch (HB) of the Z track, with a frequency of 731 +/- 20 Hz and an amplitude of 4.7(-0.6)(+0.8)% rms in the energy band 5.0-60 keV. Further to the right on the HB, at somewhat higher count rates, an additional peak at 532 +/- 43 Hz was detected with an rms amplitude of 3.0(-0.7)(+1.0). When the source moved down the HB, thus when the inferred mass accretion rate increased, the frequency of the higher frequency QPO increased to 839 +/- 13 Hz, and its amplitude decreased to 3.5(-0.3)(+0.4)% rms. The higher frequency QPO was also detected on the upper normal branch (NB) with an rms amplitude of 1.8(-0.4)(+0.6)% and a frequency of 1007 +/- 15 Hz; its peak width did not show a clear correlation with inferred mass accretion rate. The lower frequency QPO was most of the time undetectable, with typical upper limits of 2% rms; no conclusion on how this QPO behaved with mass accretion rate can be drawn. If the peak separation between the QPOs is the neutron star spin frequency (as required in some beat-frequency models), then the neutron star spin period is 2.9 +/- 0.2 ms (346 +/- 29 Hz). This discovery makes Cyg X-2 the fourth Z source that displays kHz QPOs. The properties of the kHz QPOs in Cyg X-2 are similar to those of other Z sources.