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.9 x 10(-4) (m2s 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.