A system that implements a data storage service may store data on behalf of storage service clients. The system may maintain data in multiple replicas of partitions that are stored on respective computing nodes in the system. The system may split a data partition into two new partitions, and may split the replica group that stored the original partitions into two new replica groups, each storing one of the new partitions. To split the replica group, the master replica may propagate membership changes to the other members of the replica group for adding members to the original replica group and for splitting the expanded replica group into two new replica groups. Subsequent to the split, replicas may attempt to become the master for the original replica group or for a new replica group. If an attempt to become master replica for the original replica group succeeds, the split may fail.