Live migration of log-based consistency mechanisms may be implemented for data stores. A log describing changes to replicas of data maintained at different nodes may be implemented in different ways. While the nodes are available for servicing access requests, a migration of consistent maintained between one instance of a log and a different instance of the log may be performed. A change may be committed to the current instance of the log identifying the new instance of the log as describing changes to the log subsequent to the migration. Upon completing migration, the data may be consistently maintained according to the different instance of the log.