1. A non-transitory computer-readable medium having stored thereon instructions that, when executed by a processor of a computing system of a data storage service, cause the computing system to: create, by the computing system of the data storage service, a block data storage volume on a single initial storage system for use over one or more networks by a program executing on a first computing system of a program execution service; provide, by the computing system of the data storage service to a node manager module associated with the first computing system, information that initiates creation of a logical block data storage device on the first computing system to represent the block data storage volume; respond, by the computing system of the data storage service, to an initial data access request from the program to the block data storage volume by performing the initial data access request on the block data storage volume on the initial storage system; after responding to the initial data access request, determine, by the computing system of the data storage service, to move the block data storage volume from the initial storage system to a single distinct first storage system of the data storage service, the determining being performed while the initial storage system is available for use and being based at least in part on one or more capabilities of the available initial storage system; initiate the move of the block data storage volume to the first storage system; provide, by the computing system of the data storage service to the node manager module, updated information to reflect the logical block data storage device representing the moved block data storage volume on the first storage system; and respond, by the computing system of the data storage service after the move of the block data storage volume to the first storage system, to a subsequent first data access request from the program to the block data storage volume by initiating performance of the first data access request on the block data storage volume on the first storage system, and wherein the program initiates the initial and first data access requests by interacting with the logical block data storage device, to cause the initial and first data access requests to be sent over the one or more networks to the data storage service.