The first measurement of event-by-event antideuteron number fluctuations in high energy heavy-ion collisions is presented. The measurements are carried out at midrapidity (|η|<0.8) as a function of collision centrality in Pb-Pb collisions at sqrt[s_{NN}]=5.02 TeV using the ALICE detector. A significant negative correlation between the produced antiprotons and antideuterons is observed in all collision centralities. The results are compared with a state-of-the-art coalescence calculation. While it describes the ratio of higher order cumulants of the antideuteron multiplicity distribution, it fails to describe quantitatively the magnitude of the correlation between antiproton and antideuteron production. On the other hand, thermal-statistical model calculations describe all the measured observables within uncertainties only for correlation volumes that are different with respect to those describing proton yields and a similar measurement of net-proton number fluctuations.