High precision cosmic-ray low energy antiproton fluxes reported by BESS-Polar, PAMELA and AMS-02 are consistent with secondary production from interactions of primary cosmic rays with the interstellar medium. This severely constrains the possibility of antiprotons of primary origin such as annihilation or decay of supersymmetric dark matter or evaporation of primordial black holes. In the case of antideuterons, secondary production in collisions is strongly suppressed, especially at low energies, because of the very low production cross-section and strict kinematic requirements compared to antiproton production. The lack of secondary background would imply that there is still plenty of room to search for primary antideuterons from novel production processes. The most sensitive search ever realized was reported by using the BESS flight data obtained during the previous solar minimum period in 1997. By comparison, the BESS-Polar II flight in 2007/2008 accumulated cosmic-ray data in near solar minimum conditions with more than ten times the statistics of BESS97. We will report the result of a new search for antideuterons with unprecedented sensitivity by using BESS-Polar II data.