A distributed storage system including support for distinct storage classes. A system may implement a web services interface, a number of storage nodes and a coordinator. The web services interface may receive, according to a web services protocol, client requests to store data objects. A request for a given object may include an indication of a particular storage class to be associated with the given object, and where each storage class respectively specifies one or more service level agreement (SLA) characteristics. The storage nodes may store replicas of the data objects. The coordinator may receive the client requests to store the data objects from the web services interface, where in response to the given client request, the coordinator may store one or more replicas of the given data object among the storage nodes according to the SLA characteristics specified by the particular storage class.