diff --git a/src/radix.h b/src/radix.h
--- a/src/radix.h
+++ b/src/radix.h
@@ -90,6 +90,46 @@
         return const_cast<RadixTree *>(this)->get(key);
     }
 
+    /**
+     * Remove an element from the tree.
+     * Returns true if the element was removed from the tree, false if the
+     * element wasn't found in the tree.
+     */
+    bool remove(const K &key) {
+        uint32_t level = TOP_LEVEL;
+
+        RCULock lock;
+        std::atomic<RadixElement> *eptr = &root;
+
+        RadixElement e = eptr->load();
+
+        // Walk down the tree until we find a leaf for our node.
+        while (e.isNode()) {
+        Node:
+            eptr = e.getNode()->get(level--, key);
+            e = eptr->load();
+        }
+
+        T *leaf = e.getLeaf();
+        if (leaf == nullptr || leaf->getId() != key) {
+            // We failed to find the proper element.
+            return false;
+        }
+
+        // We have the proper element, try to delete it.
+        if (eptr->compare_exchange_strong(e, RadixElement())) {
+            return true;
+        }
+
+        // The element was replaced, either by a subtree or another element.
+        if (e.isNode()) {
+            goto Node;
+        }
+
+        // The element in the slot is not the one we are looking for.
+        return false;
+    }
+
 private:
     bool insert(const K &key, T *value) {
         uint32_t level = TOP_LEVEL;
diff --git a/src/test/radix_tests.cpp b/src/test/radix_tests.cpp
--- a/src/test/radix_tests.cpp
+++ b/src/test/radix_tests.cpp
@@ -161,6 +161,94 @@
     testGet<uint64_t>();
 }
 
+template <typename K> void testRemove() {
+    typedef TestElement<K> E;
+    RadixTree<E> mytree;
+
+    E zero(0);
+    E one(1);
+    E two(2);
+    E three(3);
+
+    // Removing an element that isn't in the tree returns false.
+    BOOST_CHECK(!mytree.remove(1));
+
+    // Insert an element into the tree and check you can remove it.
+    BOOST_CHECK(mytree.insert(&one));
+    BOOST_CHECK(mytree.remove(1));
+    BOOST_CHECK_EQUAL(mytree.get(1), NULLPTR(E));
+
+    // Insert several elements and remove them.
+    BOOST_CHECK(mytree.insert(&zero));
+    BOOST_CHECK(mytree.insert(&one));
+    BOOST_CHECK(mytree.insert(&two));
+    BOOST_CHECK(mytree.insert(&three));
+
+    BOOST_CHECK(mytree.remove(0));
+    BOOST_CHECK(mytree.remove(1));
+    BOOST_CHECK(mytree.remove(2));
+    BOOST_CHECK(mytree.remove(3));
+
+    BOOST_CHECK_EQUAL(mytree.get(0), NULLPTR(E));
+    BOOST_CHECK_EQUAL(mytree.get(1), NULLPTR(E));
+    BOOST_CHECK_EQUAL(mytree.get(2), NULLPTR(E));
+    BOOST_CHECK_EQUAL(mytree.get(3), NULLPTR(E));
+
+    // Once the elements are removed, removing them again returns false.
+    BOOST_CHECK(!mytree.remove(0));
+    BOOST_CHECK(!mytree.remove(1));
+    BOOST_CHECK(!mytree.remove(2));
+    BOOST_CHECK(!mytree.remove(3));
+
+    // Check extreme values.
+    typedef typename std::make_signed<K>::type SK;
+    K maxsk = std::numeric_limits<SK>::max();
+    K minsk = std::numeric_limits<SK>::min();
+    typedef typename std::make_unsigned<K>::type UK;
+    K maxuk = std::numeric_limits<UK>::max();
+
+    E maxsigned(maxsk);
+    E minsigned(minsk);
+    E minusone(maxuk);
+    E minustwo(maxuk - 1);
+
+    // Insert them all.
+    BOOST_CHECK(mytree.insert(&zero));
+    BOOST_CHECK(mytree.insert(&one));
+    BOOST_CHECK(mytree.insert(&two));
+    BOOST_CHECK(mytree.insert(&three));
+    BOOST_CHECK(mytree.insert(&maxsigned));
+    BOOST_CHECK(mytree.insert(&minsigned));
+    BOOST_CHECK(mytree.insert(&minusone));
+    BOOST_CHECK(mytree.insert(&minustwo));
+
+    // Delete them all
+    BOOST_CHECK(mytree.remove(0));
+    BOOST_CHECK(mytree.remove(1));
+    BOOST_CHECK(mytree.remove(2));
+    BOOST_CHECK(mytree.remove(3));
+    BOOST_CHECK(mytree.remove(maxsk));
+    BOOST_CHECK(mytree.remove(minsk));
+    BOOST_CHECK(mytree.remove(maxuk));
+    BOOST_CHECK(mytree.remove(maxuk - 1));
+
+    BOOST_CHECK_EQUAL(mytree.get(0), NULLPTR(E));
+    BOOST_CHECK_EQUAL(mytree.get(1), NULLPTR(E));
+    BOOST_CHECK_EQUAL(mytree.get(2), NULLPTR(E));
+    BOOST_CHECK_EQUAL(mytree.get(3), NULLPTR(E));
+    BOOST_CHECK_EQUAL(mytree.get(maxsk), NULLPTR(E));
+    BOOST_CHECK_EQUAL(mytree.get(minsk), NULLPTR(E));
+    BOOST_CHECK_EQUAL(mytree.get(maxuk), NULLPTR(E));
+    BOOST_CHECK_EQUAL(mytree.get(maxuk - 1), NULLPTR(E));
+}
+
+BOOST_AUTO_TEST_CASE(remove_test) {
+    testRemove<int32_t>();
+    testRemove<uint32_t>();
+    testRemove<int64_t>();
+    testRemove<uint64_t>();
+}
+
 #define THREADS 128
 #define ELEMENTS 65536
 
@@ -182,18 +270,28 @@
             for (int j = 0; j < ELEMENTS; j++) {
                 rand = next(rand);
                 uint32_t v(rand >> 32);
+
+                if (mytree.remove(v)) {
+                    success--;
+                    std::this_thread::yield();
+                }
+
                 std::unique_ptr<E> ptr = MakeUnique<E>(v);
                 if (mytree.insert(ptr.get())) {
                     success++;
-                    ptr.release();
                     std::this_thread::yield();
                 }
 
-                // Regardless if we inserted or someone else did, the element
-                // should now be in the tree. For some reason, boost is spewing
-                // an inordinate amount of log when performing checks in other
-                // threads than the main one, so we'll use asserts.
-                assert(mytree.get(v)->getId() == v);
+                if (mytree.remove(v)) {
+                    success--;
+                    RCULock::synchronize();
+                }
+
+                if (mytree.insert(ptr.get())) {
+                    success++;
+                    ptr.release();
+                    std::this_thread::yield();
+                }
             }
         }));
     }