We performed a search for cosmic-ray antideuterons using data collected during four BESS balloon flights from 1997 to 2000. No candidate was found. We derived, for the first time, an upper limit of 1.9E-4 (m^2 s sr GeV/nucleon)^(-1) for the differential flux of cosmic-ray antideuterons, at the 95% confidence level, between 0.17 and 1.15 GeV/nucleon at the top of the atmosphere.