A correctly working Domain Name System (DNS) is essential for the Internet. Due to its significance and because of deficiencies in its current design, the DNS is vulnerable to a wide range of attacks. This paper presents the design and implementation of a secure distributed name service on the level of a DNS zone. Our service is able to provide fault tolerance and security even in the presence of a fraction of corrupted name servers, avoiding any single point of failure. It further solves the problem of storing zone secrets online without leaking them to a corrupted server, while still supporting secure dynamic updates. Our service uses state-machine replication and threshold cryptography. We present results from experiments performed using a prototype implementation on the Internet in realistic setups. The results show that our design achieves the required assurances while servicing the most frequent requests in reasonable time.