We present first calculations of new long-distance contributions to B s ->γγ decay due to intermediate D s and D s * meson states. The relevant γ vertices are estimated using charge couplings and transition moment couplings. Within our uncertainties, we find that these long-distance contributions could be comparable to the known short-distance contributions. Since they have different Cabibbo-Kobayashi-Maskawa matrix-element factors, there may be an interesting possibility of observing CP violation in this decay.