diff --git a/src/base58.h b/src/base58.h
--- a/src/base58.h
+++ b/src/base58.h
@@ -19,7 +19,6 @@
 #include "chainparams.h"
 #include "key.h"
 #include "pubkey.h"
-#include "script/script.h"
 #include "script/standard.h"
 #include "support/allocators/zeroafterfree.h"
 
diff --git a/src/base58.cpp b/src/base58.cpp
--- a/src/base58.cpp
+++ b/src/base58.cpp
@@ -5,6 +5,7 @@
 #include "base58.h"
 
 #include "hash.h"
+#include "script/script.h"
 #include "uint256.h"
 
 #include <boost/variant/apply_visitor.hpp>
@@ -208,85 +209,57 @@
 }
 
 namespace {
-/**
- * base58-encoded Bitcoin addresses.
- * Public-key-hash-addresses have version 0 (or 111 testnet).
- * The data vector contains RIPEMD160(SHA256(pubkey)), where pubkey is the
- * serialized public key.
- * Script-hash-addresses have version 5 (or 196 testnet).
- * The data vector contains RIPEMD160(SHA256(cscript)), where cscript is the
- * serialized redemption script.
- */
-class CBitcoinAddress : public CBase58Data {
-public:
-    bool Set(const CKeyID &id);
-    bool Set(const CScriptID &id);
-    bool Set(const CTxDestination &dest);
-    bool IsValid() const;
-    bool IsValid(const CChainParams &params) const;
-
-    CBitcoinAddress() {}
-    CBitcoinAddress(const CTxDestination &dest) { Set(dest); }
-    CBitcoinAddress(const std::string &strAddress) { SetString(strAddress); }
-    CBitcoinAddress(const char *pszAddress) { SetString(pszAddress); }
-
-    CTxDestination Get() const;
-};
-
-class CBitcoinAddressVisitor : public boost::static_visitor<bool> {
+class DestinationEncoder : public boost::static_visitor<std::string> {
 private:
-    CBitcoinAddress *addr;
+    const CChainParams &m_params;
 
 public:
-    CBitcoinAddressVisitor(CBitcoinAddress *addrIn) : addr(addrIn) {}
-
-    bool operator()(const CKeyID &id) const { return addr->Set(id); }
-    bool operator()(const CScriptID &id) const { return addr->Set(id); }
-    bool operator()(const CNoDestination &no) const { return false; }
-};
-
-} // anon namespace
+    DestinationEncoder(const CChainParams &params) : m_params(params) {}
 
-bool CBitcoinAddress::Set(const CKeyID &id) {
-    SetData(Params().Base58Prefix(CChainParams::PUBKEY_ADDRESS), &id, 20);
-    return true;
-}
-
-bool CBitcoinAddress::Set(const CScriptID &id) {
-    SetData(Params().Base58Prefix(CChainParams::SCRIPT_ADDRESS), &id, 20);
-    return true;
-}
-
-bool CBitcoinAddress::Set(const CTxDestination &dest) {
-    return boost::apply_visitor(CBitcoinAddressVisitor(this), dest);
-}
+    std::string operator()(const CKeyID &id) const {
+        std::vector<uint8_t> data =
+            m_params.Base58Prefix(CChainParams::PUBKEY_ADDRESS);
+        data.insert(data.end(), id.begin(), id.end());
+        return EncodeBase58Check(data);
+    }
 
-bool CBitcoinAddress::IsValid() const {
-    return IsValid(Params());
-}
+    std::string operator()(const CScriptID &id) const {
+        std::vector<uint8_t> data =
+            m_params.Base58Prefix(CChainParams::SCRIPT_ADDRESS);
+        data.insert(data.end(), id.begin(), id.end());
+        return EncodeBase58Check(data);
+    }
 
-bool CBitcoinAddress::IsValid(const CChainParams &params) const {
-    bool fCorrectSize = vchData.size() == 20;
-    bool fKnownVersion =
-        vchVersion == params.Base58Prefix(CChainParams::PUBKEY_ADDRESS) ||
-        vchVersion == params.Base58Prefix(CChainParams::SCRIPT_ADDRESS);
-    return fCorrectSize && fKnownVersion;
-}
+    std::string operator()(const CNoDestination &no) const { return ""; }
+};
 
-CTxDestination CBitcoinAddress::Get() const {
-    if (!IsValid()) return CNoDestination();
-    uint160 id;
-    memcpy(&id, &vchData[0], 20);
-    if (vchVersion == Params().Base58Prefix(CChainParams::PUBKEY_ADDRESS)) {
-        return CKeyID(id);
-    } else if (vchVersion ==
-               Params().Base58Prefix(CChainParams::SCRIPT_ADDRESS)) {
-        return CScriptID(id);
-    } else {
+CTxDestination DecodeDestination(const std::string &str,
+                                 const CChainParams &params) {
+    std::vector<uint8_t> data;
+    uint160 hash;
+    if (!DecodeBase58Check(str, data)) {
         return CNoDestination();
     }
+    // Base58Check decoding
+    const std::vector<uint8_t> &pubkey_prefix =
+        params.Base58Prefix(CChainParams::PUBKEY_ADDRESS);
+    if (data.size() == 20 + pubkey_prefix.size() &&
+        std::equal(pubkey_prefix.begin(), pubkey_prefix.end(), data.begin())) {
+        memcpy(hash.begin(), &data[pubkey_prefix.size()], 20);
+        return CKeyID(hash);
+    }
+    const std::vector<uint8_t> &script_prefix =
+        params.Base58Prefix(CChainParams::SCRIPT_ADDRESS);
+    if (data.size() == 20 + script_prefix.size() &&
+        std::equal(script_prefix.begin(), script_prefix.end(), data.begin())) {
+        memcpy(hash.begin(), &data[script_prefix.size()], 20);
+        return CScriptID(hash);
+    }
+    return CNoDestination();
 }
 
+} // namespace
+
 void CBitcoinSecret::SetKey(const CKey &vchSecret) {
     assert(vchSecret.IsValid());
     SetData(Params().Base58Prefix(CChainParams::SECRET_KEY), vchSecret.begin(),
@@ -319,19 +292,18 @@
 }
 
 std::string EncodeDestination(const CTxDestination &dest) {
-    CBitcoinAddress addr(dest);
-    return addr.IsValid() ? addr.ToString() : "";
+    return boost::apply_visitor(DestinationEncoder(Params()), dest);
 }
 
 CTxDestination DecodeDestination(const std::string &str) {
-    return CBitcoinAddress(str).Get();
+    return DecodeDestination(str, Params());
 }
 
 bool IsValidDestinationString(const std::string &str,
                               const CChainParams &params) {
-    return CBitcoinAddress(str).IsValid(params);
+    return IsValidDestination(DecodeDestination(str, params));
 }
 
 bool IsValidDestinationString(const std::string &str) {
-    return CBitcoinAddress(str).IsValid();
+    return IsValidDestination(DecodeDestination(str, Params()));
 }