The coordinated introduction of sperm and eggs is a prerequisite of high fertilization efficiency. In Drosophila melanogaster, as in most internally fertilizing animals, mated females store sperm prior to fertilization. Yet the regulation of sperm exit from these storage sites is poorly understood. To test one likely factor that could coordinate gamete availability, we quantified sperm exit from storage in three types of female: genetically matched females that were normal or eggless, and an additional wild-type control. Long-term depletion of sperm stores in normal females and eggless females occurs at similar rates. However, soon after mating, egg presence appears to accelerate the transition from one storage stage to the next. Since male ejaculate components and female factors contribute to sperm depletion, opportunities exist for both cooperation and conflict between the sexes in sperm storage dynamics.