  We present first calculations of new long-distance contributions to $B_s \to
\gamma \gamma$ decay due to intermediate $D_s$ and $D_s^*$ meson states. The
relevant $\gamma$ 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.
