Despite the scalability, availability and resiliency potential suggested by Distributed Hash Tables, their lack of support for replication of mutable data and for strong consistency models stands in the way of their becoming widely accepted as a viable basis for the future generation Internet. This paper presents PaxonDHT, a Paxos-based middleware service, which ensures with high probability that a dynamic set of replicas reach total order agreement. PaxonDHT works well in the highly dynamic environment of DHTs, preserving the properties of the underlying DHT layer, and provides simultaneous support for heterogeneous services. Our algorithm has been deployed on Pastry, using the Common API for interoperability with other DHTs. Experimental results in a simulated network show that PaxonDHT is scalable with replica set size and system load, and that it works well in highly dynamic environments.