We searched for antideuterons (d[over ¯]'s) in the 4.7×10^{9} cosmic-ray events observed during the BESS-Polar II flight at solar minimum in 2007-2008 but found no candidates. The resulting 95% C.L. upper limit on the d[over ¯] flux is 6.7×10^{-5} (m^{2} s sr GeV/n)^{-1} in an energy range from 0.163 to 1.100 GeV/n. The result has improved by more than a factor of 14 from the upper limit of BESS97, which had a potential comparable to that of BESS-Polar II in the search for cosmic-origin d[over ¯]'s and was conducted during the former solar minimum. The upper limit of d[over ¯] flux from BESS-Polar II is the first result achieving the sensitivity to constrain the latest theoretical predictions.