Mars Global Surveyor is providing the first observations of transient eddies in the southern hemisphere of Mars. We derive basic properties of the traveling eddies that appear in midwinter (Ls = 134¿--148¿) through analysis of radio occultation measurements at 67¿--70¿S latitude. The dominant mode has a period of ~2 solar days and a zonal wavenumber s = 3. Strong zonal variations in eddy amplitude signal the presence of a possible storm zone at 150¿--330¿E longitude. Within this longitude band the eddies achieve peak amplitudes at the 300-Pa pressure level of ~7 K in temperature and 10--15 m s-1 in meridional wind speed. The minimum temperature associated with the eddies is ~2 K colder than saturation of CO2, close to the threshold where nucleation and growth of new ice particles can occur. A simulation by a Mars general circulation model produces traveling eddies that closely resemble the observations.