diff --git a/daemon/table/fib.cpp b/daemon/table/fib.cpp
index 99a1bf9..c28a695 100644
--- a/daemon/table/fib.cpp
+++ b/daemon/table/fib.cpp
@@ -143,26 +143,21 @@
 void
 Fib::removeNextHopFromAllEntries(shared_ptr<Face> face)
 {
-  shared_ptr<fib::Entry> toErase;
+  std::list<fib::Entry*> toErase;
 
   auto&& enumerable = m_nameTree.fullEnumerate(&predicate_NameTreeEntry_hasFibEntry);
   for (const name_tree::Entry& nte : enumerable) {
-    if (toErase != nullptr) {
-      this->erase(*toErase);
-      toErase.reset();
-    }
-
     shared_ptr<fib::Entry> entry = nte.getFibEntry();
     entry->removeNextHop(face);
     if (!entry->hasNextHops()) {
-      toErase = entry;
-      // entry needs to be erased, but we must wait until next iteration
-      // to erase it because otherwise it would invalidate the iterator
+      toErase.push_back(entry.get());
+      // entry needs to be erased, but we must wait until the enumeration ends,
+      // because otherwise NameTree iterator would be invalidated
     }
   }
 
-  if (toErase != nullptr) {
-    this->erase(*toErase);
+  for (fib::Entry* entry : toErase) {
+    this->erase(*entry);
   }
 }
 
diff --git a/tests/daemon/table/fib.cpp b/tests/daemon/table/fib.cpp
index 35fcd3e..d75088b 100644
--- a/tests/daemon/table/fib.cpp
+++ b/tests/daemon/table/fib.cpp
@@ -264,6 +264,22 @@
   BOOST_CHECK_EQUAL(entry->getPrefix(), nameEmpty);
 }
 
+BOOST_AUTO_TEST_CASE(RemoveNextHopFromManyEntries)
+{
+  NameTree nameTree(16);
+  Fib fib(nameTree);
+  shared_ptr<Face> face1 = make_shared<DummyFace>();
+
+  for (uint64_t i = 0; i < 300; ++i) {
+    shared_ptr<fib::Entry> entry = fib.insert(Name("/P").appendVersion(i)).first;
+    entry->addNextHop(face1, 0);
+  }
+  BOOST_CHECK_EQUAL(fib.size(), 300);
+
+  fib.removeNextHopFromAllEntries(face1);
+  BOOST_CHECK_EQUAL(fib.size(), 0);
+}
+
 void
 validateFindExactMatch(const Fib& fib, const Name& target)
 {