We have measured the beam-normal single-spin asymmetry An in the elastic scattering of 1–3 GeV transversely polarized electrons from H1 and for the first time from He4, C12, and Pb208. For H1, He4, and C12, the measurements are in agreement with calculations that relate An to the imaginary part of the two-photon exchange amplitude including inelastic intermediate states. Surprisingly, the Pb208 result is significantly smaller than the corresponding prediction using the same formalism. These results suggest that a systematic set of new Anmeasurements might emerge as a new and sensitive probe of the structure of heavy nuclei.