The cross section for anti-deuteron photoproduction is measured at HERA at a mean centre-of-mass energy of GeV in the range 0.2 < p T /M < 0.7 and |y| < 0.4, where M, p T and y are the mass, transverse momentum and rapidity of the anti-deuteron in the HERA laboratory frame, respectively. The numbers of anti-deuterons per event are found to be similar in photoproduction to those in central proton-proton collisions at the CERN ISR but much lower than those in central Au-Au collisions at RHIC. The coalescence parameter B 2, which characterizes the likelihood of anti-deuteron production, is measured in photoproduction to be , which is much higher than in Au-Au collisions at a similar nucleon-nucleon centre-of-mass energy. No significant production of particles heavier than deuterons is observed and upper limits are set on the photoproduction cross sections for such particles.