A replicated database can be provisioned that provides primary and secondary replicas that can be provisioned in different data zones or geographical locations. The database can be installed on the primary replica, and both the primary and secondary replica can have installed a block level replication mechanism that allows any I/O operation to be replicated by between the primary and secondary replicas. Any failure or outage of the primary replica can be addressed by performing a failover operation to the secondary replica. A DNS name or other such approach can be used such that the name can be aliased to the secondary replica during a failover, such that there is no action needed on the part of the customer to utilize the “new” primary replica. The creation of the database and provisioning of the replicated instance can be initiated using a Web service call to a control environment. A replicated database can also be scaled according to storage or computing capacity with no disruption of service using a Web service call to the control environment.