In most cosmological models, primordial black holes (PBHs) should have formed in the early Universe. Their Hawking evaporation into particles could eventually lead to the formation of antideuterium nuclei. This paper is devoted to a first computation of this antideuteron flux. The production of these antinuclei is studied with a simple coalescence scheme, and their propagation in the Galaxy is treated with a well-constrained diffusion model. We compare the resulting primary flux to the secondary background, due to the spallation of protons on the interstellar matter. Antideuterons are shown to be a very sensitive probe for primordial black holes in our Galaxy. The next generation of experiments should allow investigators to significantly improve the current upper limit, nor even provide the first evidence of the existence of evaporating black holes.