We investigate the cosmological consequences of a theory in which the electric charge e can vary. In this theory the fine structure "constant," alpha, remains almost constant in the radiation era, undergoes a small increase in the matter era, but approaches a constant value when the universe starts accelerating because of a positive cosmological constant. This model satisfies geonuclear, nucleosynthesis, and cosmic microwave background constraints on time variation in alpha, while fitting the observed accelerating Universe and evidence for small alpha variations in quasar spectra. It also places specific restrictions on the nature of the dark matter. Further tests, involving stellar spectra and Eötvös experiments, are proposed.