diff --git a/src/addrman.h b/src/addrman.h
--- a/src/addrman.h
+++ b/src/addrman.h
@@ -174,6 +174,10 @@
 //! ... in at least this many days
 #define ADDRMAN_MIN_FAIL_DAYS 7
 
+//! how recent a successful connection should be before we allow an address to
+//! be evicted from tried
+#define ADDRMAN_REPLACEMENT_SECONDS (4 * 60 * 60)
+
 //! the maximum percentage of nodes to return in a getaddr call
 #define ADDRMAN_GETADDR_MAX_PCT 23
 
@@ -185,6 +189,9 @@
 #define ADDRMAN_NEW_BUCKET_COUNT (1 << ADDRMAN_NEW_BUCKET_COUNT_LOG2)
 #define ADDRMAN_BUCKET_SIZE (1 << ADDRMAN_BUCKET_SIZE_LOG2)
 
+//! the maximum number of tried addr collisions to store
+#define ADDRMAN_SET_TRIED_COLLISION_SIZE 10
+
 /**
  * Stochastical (IP) address manager
  */
@@ -220,6 +227,10 @@
     //! last time Good was called (memory only)
     int64_t nLastGood;
 
+    //! Holds addrs inserted into tried table that collide with existing
+    //! entries. Test-before-evict discpline used to resolve these collisions.
+    std::set<int> m_tried_collisions;
+
 protected:
     //! secret key to randomize bucket select with
     uint256 nKey;
@@ -249,7 +260,7 @@
     void ClearNew(int nUBucket, int nUBucketPos);
 
     //! Mark an entry "good", possibly moving it from "new" to "tried".
-    void Good_(const CService &addr, int64_t nTime);
+    void Good_(const CService &addr, bool test_before_evict, int64_t time);
 
     //! Add an entry to the "new" table.
     bool Add_(const CAddress &addr, const CNetAddr &source,
@@ -262,6 +273,13 @@
     //! table is selected from.
     CAddrInfo Select_(bool newOnly);
 
+    //! See if any to-be-evicted tried table entries have been tested and if so
+    //! resolve the collisions.
+    void ResolveCollisions_();
+
+    //! Return a random to-be-evicted tried table address.
+    CAddrInfo SelectTriedCollision_();
+
     //! Wraps GetRandInt to allow tests to override RandomInt and make it
     //! determinismistic.
     virtual int RandomInt(int nMax);
@@ -558,10 +576,11 @@
     }
 
     //! Mark an entry as accessible.
-    void Good(const CService &addr, int64_t nTime = GetAdjustedTime()) {
+    void Good(const CService &addr, bool test_before_evict = true,
+              int64_t nTime = GetAdjustedTime()) {
         LOCK(cs);
         Check();
-        Good_(addr, nTime);
+        Good_(addr, test_before_evict, nTime);
         Check();
     }
 
@@ -574,6 +593,28 @@
         Check();
     }
 
+    //! See if any to-be-evicted tried table entries have been tested and if so
+    //! resolve the collisions.
+    void ResolveCollisions() {
+        LOCK(cs);
+        Check();
+        ResolveCollisions_();
+        Check();
+    }
+
+    //! Randomly select an address in tried that another address is attempting
+    //! to evict.
+    CAddrInfo SelectTriedCollision() {
+        CAddrInfo ret;
+        {
+            LOCK(cs);
+            Check();
+            ret = SelectTriedCollision_();
+            Check();
+        }
+        return ret;
+    }
+
     /**
      * Choose an address to connect to.
      */
diff --git a/src/addrman.cpp b/src/addrman.cpp
--- a/src/addrman.cpp
+++ b/src/addrman.cpp
@@ -215,7 +215,8 @@
     info.fInTried = true;
 }
 
-void CAddrMan::Good_(const CService &addr, int64_t nTime) {
+void CAddrMan::Good_(const CService &addr, bool test_before_evict,
+                     int64_t nTime) {
     int nId;
 
     nLastGood = nTime;
@@ -265,10 +266,25 @@
         return;
     }
 
-    LogPrint(BCLog::ADDRMAN, "Moving %s to tried\n", addr.ToString());
+    // which tried bucket to move the entry to
+    int tried_bucket = info.GetTriedBucket(nKey);
+    int tried_bucket_pos = info.GetBucketPosition(nKey, false, tried_bucket);
+
+    // Will moving this address into tried evict another entry?
+    if (test_before_evict && (vvTried[tried_bucket][tried_bucket_pos] != -1)) {
+        LogPrint(BCLog::ADDRMAN, "addrman", "Collision inserting element into "
+                                            "tried table, moving %s to "
+                                            "m_tried_collisions=%d\n",
+                 addr.ToString(), m_tried_collisions.size());
+        if (m_tried_collisions.size() < ADDRMAN_SET_TRIED_COLLISION_SIZE) {
+            m_tried_collisions.insert(nId);
+        }
+    } else {
+        LogPrint(BCLog::ADDRMAN, "Moving %s to tried\n", addr.ToString());
 
-    // move nId to the tried tables
-    MakeTried(info, nId);
+        // move nId to the tried tables
+        MakeTried(info, nId);
+    }
 }
 
 bool CAddrMan::Add_(const CAddress &addr, const CNetAddr &source,
@@ -612,3 +628,97 @@
 int CAddrMan::RandomInt(int nMax) {
     return GetRandInt(nMax);
 }
+
+void CAddrMan::ResolveCollisions_() {
+    const int64_t adjustedTime = GetAdjustedTime();
+
+    for (std::set<int>::iterator it = m_tried_collisions.begin();
+         it != m_tried_collisions.end();) {
+        int id_new = *it;
+
+        bool erase_collision = false;
+
+        // If id_new not found in mapInfo remove it from m_tried_collisions.
+        auto id_new_it = mapInfo.find(id_new);
+        if (id_new_it == mapInfo.end()) {
+            erase_collision = true;
+        } else {
+            CAddrInfo &info_new = id_new_it->second;
+
+            // Which tried bucket to move the entry to.
+            int tried_bucket = info_new.GetTriedBucket(nKey);
+            int tried_bucket_pos =
+                info_new.GetBucketPosition(nKey, false, tried_bucket);
+            if (!info_new.IsValid()) {
+                // id_new may no longer map to a valid address
+                erase_collision = true;
+            } else if (vvTried[tried_bucket][tried_bucket_pos] != -1) {
+                // The position in the tried bucket is not empty
+
+                // Get the to-be-evicted address that is being tested
+                int id_old = vvTried[tried_bucket][tried_bucket_pos];
+                CAddrInfo &info_old = mapInfo[id_old];
+
+                // Has successfully connected in last X hours
+                if (adjustedTime - info_old.nLastSuccess <
+                    ADDRMAN_REPLACEMENT_SECONDS) {
+                    erase_collision = true;
+                } else if (adjustedTime - info_old.nLastTry <
+                           ADDRMAN_REPLACEMENT_SECONDS) {
+                    // attempted to connect and failed in last X hours
+
+                    // Give address at least 60 seconds to successfully connect
+                    if (GetAdjustedTime() - info_old.nLastTry > 60) {
+                        LogPrint(BCLog::ADDRMAN, "addrman",
+                                 "Swapping %s for %s in tried table\n",
+                                 info_new.ToString(), info_old.ToString());
+
+                        // Replaces an existing address already in the tried
+                        // table with the new address
+                        Good_(info_new, false, GetAdjustedTime());
+                        erase_collision = true;
+                    }
+                }
+            } else {
+                // Collision is not actually a collision anymore
+                Good_(info_new, false, adjustedTime);
+                erase_collision = true;
+            }
+        }
+
+        if (erase_collision) {
+            m_tried_collisions.erase(it++);
+        } else {
+            it++;
+        }
+    }
+}
+
+CAddrInfo CAddrMan::SelectTriedCollision_() {
+    if (m_tried_collisions.size() == 0) {
+        return CAddrInfo();
+    }
+
+    std::set<int>::iterator it = m_tried_collisions.begin();
+
+    // Selects a random element from m_tried_collisions.
+    std::advance(it, GetRandInt(m_tried_collisions.size()));
+    int id_new = *it;
+
+    // If id_new not found in mapInfo remove it from m_tried_collisions.
+    auto id_new_it = mapInfo.find(id_new);
+    if (id_new_it == mapInfo.end()) {
+        m_tried_collisions.erase(it);
+        return CAddrInfo();
+    }
+
+    CAddrInfo &newInfo = id_new_it->second;
+
+    // which tried bucket to move the entry to
+    int tried_bucket = newInfo.GetTriedBucket(nKey);
+    int tried_bucket_pos = newInfo.GetBucketPosition(nKey, false, tried_bucket);
+
+    int id_old = vvTried[tried_bucket][tried_bucket_pos];
+
+    return mapInfo[id_old];
+}
diff --git a/src/net.cpp b/src/net.cpp
--- a/src/net.cpp
+++ b/src/net.cpp
@@ -1920,10 +1920,17 @@
             }
         }
 
+        addrman.ResolveCollisions();
+
         int64_t nANow = GetAdjustedTime();
         int nTries = 0;
         while (!interruptNet) {
-            CAddrInfo addr = addrman.Select(fFeeler);
+            CAddrInfo addr = addrman.SelectTriedCollision();
+
+            // SelectTriedCollision returns an invalid address if it is empty.
+            if (!fFeeler || !addr.IsValid()) {
+                addr = addrman.Select(fFeeler);
+            }
 
             // if we selected an invalid address, restart
             if (!addr.IsValid() || setConnected.count(addr.GetGroup()) ||
diff --git a/src/test/addrman_tests.cpp b/src/test/addrman_tests.cpp
--- a/src/test/addrman_tests.cpp
+++ b/src/test/addrman_tests.cpp
@@ -37,6 +37,18 @@
     }
 
     void Delete(int nId) { CAddrMan::Delete(nId); }
+
+    // Simulates connection failure so that we can test eviction of offline
+    // nodes
+    void SimConnFail(CService &addr) {
+        int64_t nLastSuccess = 1;
+        // Set last good connection in the deep past.
+        Good_(addr, true, nLastSuccess);
+
+        bool count_failure = false;
+        int64_t nLastTry = GetAdjustedTime() - 61;
+        Attempt(addr, count_failure, nLastTry);
+    }
 };
 
 static CNetAddr ResolveIP(const char *ip) {
@@ -379,7 +391,7 @@
         int octet1 = i % 256;
         int octet2 = i >> 8 % 256;
         std::string strAddr =
-            boost::to_string(octet1) + "." + boost::to_string(octet2) + ".1.23";
+            std::to_string(octet1) + "." + std::to_string(octet2) + ".1.23";
         CAddress addr = CAddress(ResolveService(strAddr), NODE_NONE);
 
         // Ensure that for all addrs in addrman, isTerrible == false.
@@ -518,4 +530,152 @@
     //  than 64 buckets.
     BOOST_CHECK(buckets.size() > 64);
 }
+
+BOOST_AUTO_TEST_CASE(addrman_selecttriedcollision) {
+    CAddrManTest addrman;
+
+    // Set addrman addr placement to be deterministic.
+    addrman.MakeDeterministic();
+
+    BOOST_CHECK(addrman.size() == 0);
+
+    // Empty addrman should return blank addrman info.
+    BOOST_CHECK(addrman.SelectTriedCollision().ToString() == "[::]:0");
+
+    // Add twenty two addresses.
+    CNetAddr source = ResolveIP("252.2.2.2");
+    for (unsigned int i = 1; i < 23; i++) {
+        CService addr = ResolveService("250.1.1." + std::to_string(i));
+        addrman.Add(CAddress(addr, NODE_NONE), source);
+        addrman.Good(addr);
+
+        // No collisions yet.
+        BOOST_CHECK(addrman.size() == i);
+        BOOST_CHECK(addrman.SelectTriedCollision().ToString() == "[::]:0");
+    }
+
+    // Ensure Good handles duplicates well.
+    for (unsigned int i = 1; i < 23; i++) {
+        CService addr = ResolveService("250.1.1." + std::to_string(i));
+        addrman.Good(addr);
+
+        BOOST_CHECK(addrman.size() == 22);
+        BOOST_CHECK(addrman.SelectTriedCollision().ToString() == "[::]:0");
+    }
+}
+
+BOOST_AUTO_TEST_CASE(addrman_noevict) {
+    CAddrManTest addrman;
+
+    // Set addrman addr placement to be deterministic.
+    addrman.MakeDeterministic();
+
+    // Add twenty two addresses.
+    CNetAddr source = ResolveIP("252.2.2.2");
+    for (unsigned int i = 1; i < 23; i++) {
+        CService addr = ResolveService("250.1.1." + std::to_string(i));
+        addrman.Add(CAddress(addr, NODE_NONE), source);
+        addrman.Good(addr);
+
+        // No collision yet.
+        BOOST_CHECK(addrman.size() == i);
+        BOOST_CHECK(addrman.SelectTriedCollision().ToString() == "[::]:0");
+    }
+
+    // Collision between 23 and 19.
+    CService addr23 = ResolveService("250.1.1.23");
+    addrman.Add(CAddress(addr23, NODE_NONE), source);
+    addrman.Good(addr23);
+
+    BOOST_CHECK(addrman.size() == 23);
+    BOOST_CHECK(addrman.SelectTriedCollision().ToString() == "250.1.1.19:0");
+
+    // 23 should be discarded and 19 not evicted.
+    addrman.ResolveCollisions();
+    BOOST_CHECK(addrman.SelectTriedCollision().ToString() == "[::]:0");
+
+    // Lets create two collisions.
+    for (unsigned int i = 24; i < 33; i++) {
+        CService addr = ResolveService("250.1.1." + std::to_string(i));
+        addrman.Add(CAddress(addr, NODE_NONE), source);
+        addrman.Good(addr);
+
+        BOOST_CHECK(addrman.size() == i);
+        BOOST_CHECK(addrman.SelectTriedCollision().ToString() == "[::]:0");
+    }
+
+    // Cause a collision.
+    CService addr33 = ResolveService("250.1.1.33");
+    addrman.Add(CAddress(addr33, NODE_NONE), source);
+    addrman.Good(addr33);
+    BOOST_CHECK(addrman.size() == 33);
+
+    BOOST_CHECK(addrman.SelectTriedCollision().ToString() == "250.1.1.27:0");
+
+    // Cause a second collision.
+    addrman.Add(CAddress(addr23, NODE_NONE), source);
+    addrman.Good(addr23);
+    BOOST_CHECK(addrman.size() == 33);
+
+    BOOST_CHECK(addrman.SelectTriedCollision().ToString() != "[::]:0");
+    addrman.ResolveCollisions();
+    BOOST_CHECK(addrman.SelectTriedCollision().ToString() == "[::]:0");
+}
+
+BOOST_AUTO_TEST_CASE(addrman_evictionworks) {
+    CAddrManTest addrman;
+
+    // Set addrman addr placement to be deterministic.
+    addrman.MakeDeterministic();
+
+    BOOST_CHECK(addrman.size() == 0);
+
+    // Empty addrman should return blank addrman info.
+    BOOST_CHECK(addrman.SelectTriedCollision().ToString() == "[::]:0");
+
+    // Add twenty two addresses.
+    CNetAddr source = ResolveIP("252.2.2.2");
+    for (unsigned int i = 1; i < 23; i++) {
+        CService addr = ResolveService("250.1.1." + std::to_string(i));
+        addrman.Add(CAddress(addr, NODE_NONE), source);
+        addrman.Good(addr);
+
+        // No collision yet.
+        BOOST_CHECK(addrman.size() == i);
+        BOOST_CHECK(addrman.SelectTriedCollision().ToString() == "[::]:0");
+    }
+
+    // Collision between 23 and 19.
+    CService addr = ResolveService("250.1.1.23");
+    addrman.Add(CAddress(addr, NODE_NONE), source);
+    addrman.Good(addr);
+
+    BOOST_CHECK(addrman.size() == 23);
+    CAddrInfo info = addrman.SelectTriedCollision();
+    BOOST_CHECK(info.ToString() == "250.1.1.19:0");
+
+    // Ensure test of address fails, so that it is evicted.
+    addrman.SimConnFail(info);
+
+    // Should swap 23 for 19.
+    addrman.ResolveCollisions();
+    BOOST_CHECK(addrman.SelectTriedCollision().ToString() == "[::]:0");
+
+    // If 23 was swapped for 19, then this should cause no collisions.
+    addrman.Add(CAddress(addr, NODE_NONE), source);
+    addrman.Good(addr);
+
+    BOOST_CHECK(addrman.SelectTriedCollision().ToString() == "[::]:0");
+
+    // If we insert 19 is should collide with 23.
+    CService addr19 = ResolveService("250.1.1.19");
+    addrman.Add(CAddress(addr19, NODE_NONE), source);
+    addrman.Good(addr19);
+
+    BOOST_CHECK(addrman.SelectTriedCollision().ToString() == "250.1.1.23:0");
+
+    addrman.ResolveCollisions();
+    BOOST_CHECK(addrman.SelectTriedCollision().ToString() == "[::]:0");
+}
+
 BOOST_AUTO_TEST_SUITE_END()