A service provider network includes a database that has one or more “base” machine images and, for one or more of the base machine images, one or more predetermined “optimized” machine images. Each base and optimized machine image are stored in the database and selected based on certain user inputs to create a customer-desired virtual machine instance on a host computer. An optimized machine image is a version of a particular base machine image to which one or more optimizations have been applied. The database may contain complete optimized machine images or data bits that, when applied to a base machine image, result in the optimized machine image.