Mated females of many animal species store sperm. Sperm storage profoundly influences the number, timing, and paternity of the female's progeny. To investigate mechanisms for sperm storage in Drosophila melanogaster, we generated and analyzed mutations in Acp36DE. Acp36DE is a male seminal fluid protein whose localization in mated females suggested a role in sperm storage. We report that male-derived Acp36DE is essential for efficient sperm storage by females. Acp36DE(1) (null) mutant males produced and transferred normal amounts of sperm and seminal fluid proteins. However, mates of Acp36DE(1) males stored only 15% as many sperm and produced 10% as many adult progeny as control-mated females. Moreover, without Acp36DE, mated females failed to maintain an elevated egg-laying rate and decreased receptivity, behaviors whose persistence (but not initiation) normally depends on the presence of stored sperm. Previous studies suggested that a barrier in the oviduct confines sperm and Acp36DE to a limited area near the storage organs. We show that Acp36DE is not required for barrier formation, but both Acp36DE and the barrier are required for maximal sperm storage. Acp36DE associates tightly with sperm. Our results indicate that Acp36DE is essential for the initial storage of sperm, and that it may also influence the arrangement and retention of stored sperm.