Scale out data protection with erasure coding is presented herein. Based on an initial number of storage devices determined to have been included in an initial stage of a data storage cluster, an initial protection scheme for the initial stage can determine first coding fragment(s) for data stored within the data storage cluster to facilitate a first recovery, from the initial stage, of the data using the first coding fragment(s). Further, in response to a defined number of additional storage devices being determined to have been added to the data storage cluster to generate a modified data storage cluster, the initial protection scheme can be modified to obtain a modified protection scheme that can determine, for the modified data storage cluster, second coding fragment(s) for the data to facilitate a second recovery of the data using the first coding fragment(s) and the second coding fragment(s).