Models of optimal sperm allocation are constructed using stochastic dynamic programming techniques, yielding predictions about sperm allocation when males mate sequentially, breeding time is finite, sperm stores are limited and females vary in quality. The models suggest that uncertainty of future reproductive opportunities should favour withholding of sperm, so that males tend to allocate less (for a given level of stored sperm) earlier in the breeding season. This effect is more pronounced the greater the variance in female quality. We also show that while allocation will be influenced by mate value, it is not necessarily optimal to allocate preferentially to high-quality females, since the benefits of a higher-quality mate may be offset by increased risk of rejection of sperm or higher sperm competition. The relationship between mate quality and level of allocation will depend strongly on the amount of remaining stored sperm, with males whose supplies are depleted being more likely to favour lower-quality partners.