According to one embodiment of the present invention, a system uses parallel transaction messages for database replication. The system receives transaction messages from a source system via a plurality of parallel send queues in a receive queue. Each transaction message includes a message identifier indicating a commit order for that transaction. The system reads transaction messages in the receive queue in order in which they were committed against a source database based on the message identifier, and applies changes described by the transaction messages to a target database. Two or more transaction messages in the receive queue are applied to the target database in parallel. The system deletes transaction messages from the receive queue asynchronously to applying changes described by those transaction messages to the target database. Embodiments of the present invention further include a method and computer program product for parallel transaction messages in substantially the same manners described above.