For a given cross-data-store transaction request at a storage service, a coordinator transmits respective voting transition requests to a plurality of log-based transaction managers (LTMs) configured for the respective data stores to which writes are directed in the transaction. The LTMs transmit responses to the coordinator based on data-store-specific conflict detection performed using contents of the voting transition requests and respective data-store-specific state transition logs. The coordinator determines a termination status of the cross-data-store transaction based on the LTMs' responses, and provides an indication of the termination status to the LTMs.