A performance-based storage service level agreement (SLA) can be established that specifies one or more storage performance parameters. A storage allocation process can include receiving a request for a storage SLA that specifies one or more storage performance parameters, determining, for a virtual machine (VM) and based at least in part on the one or more storage performance parameters in the storage SLA: (i) a storage location among a set of candidate storage locations, and (ii) an amount of storage to allocate. The amount of storage can then be allocated at the storage location for the VM to use in making storage requests. Runtime enforcement of the storage SLA can utilize a scheduling mechanism that buffers individual storage requests into different queues that are used for meeting one or more storage performance requirements specified in storage SLA.