diff --git a/src/access_revocation_manager_impl.cc b/src/access_revocation_manager_impl.cc
index f039114..035e1ad 100644
--- a/src/access_revocation_manager_impl.cc
+++ b/src/access_revocation_manager_impl.cc
@@ -83,12 +83,37 @@
   store_->SaveSettings(kConfigFileName, json, callback);
 }
 
-void AccessRevocationManagerImpl::RemoveExpired() {
+void AccessRevocationManagerImpl::Shrink() {
+  base::Time oldest[2] = {base::Time::Max(), base::Time::Max()};
   for (auto i = begin(entries_); i != end(entries_);) {
     if (i->expiration <= clock_->Now())
       i = entries_.erase(i);
-    else
+    else {
+      // Non-strict comparison to ensure counting same timestamps as different.
+      if (i->revocation <= oldest[0]) {
+        oldest[1] = oldest[0];
+        oldest[0] = i->revocation;
+      } else {
+        oldest[1] = std::min(oldest[1], i->revocation);
+      }
       ++i;
+    }
+  }
+  CHECK_GT(capacity_, 1u);
+  if (entries_.size() >= capacity_) {
+    // List is full so we are going to remove oldest entries from the list.
+    for (auto i = begin(entries_); i != end(entries_);) {
+      if (i->revocation <= oldest[1])
+        i = entries_.erase(i);
+      else {
+        ++i;
+      }
+    }
+    // And replace with a single rule to block everything older.
+    Entry all_blocking_entry;
+    all_blocking_entry.expiration = base::Time::Max();
+    all_blocking_entry.revocation = oldest[1];
+    entries_.insert(all_blocking_entry);
   }
 }
 
@@ -99,8 +124,6 @@
 
 void AccessRevocationManagerImpl::Block(const Entry& entry,
                                         const DoneCallback& callback) {
-  // Iterating is OK as Save below is more expensive.
-  RemoveExpired();
   if (entry.expiration <= clock_->Now()) {
     if (!callback.is_null()) {
       ErrorPtr error;
@@ -110,15 +133,10 @@
     }
     return;
   }
-  if (entries_.size() >= capacity_) {
-    if (!callback.is_null()) {
-      ErrorPtr error;
-      Error::AddTo(&error, FROM_HERE, "blacklist_is_full",
-                   "Unable to store more entries");
-      callback.Run(std::move(error));
-    }
-    return;
-  }
+
+  // Iterating is OK as Save below is more expensive.
+  Shrink();
+  CHECK_LT(entries_.size(), capacity_);
 
   auto existing = entries_.find(entry);
   if (existing != entries_.end()) {
diff --git a/src/access_revocation_manager_impl.h b/src/access_revocation_manager_impl.h
index 0ee253e..9aed36a 100644
--- a/src/access_revocation_manager_impl.h
+++ b/src/access_revocation_manager_impl.h
@@ -36,7 +36,7 @@
  private:
   void Load();
   void Save(const DoneCallback& callback);
-  void RemoveExpired();
+  void Shrink();
 
   struct EntryIdsLess {
     bool operator()(const Entry& l, const Entry& r) const {
diff --git a/src/access_revocation_manager_impl_unittest.cc b/src/access_revocation_manager_impl_unittest.cc
index b0b774b..afc63fe 100644
--- a/src/access_revocation_manager_impl_unittest.cc
+++ b/src/access_revocation_manager_impl_unittest.cc
@@ -112,29 +112,46 @@
                   }));
 }
 
-TEST_F(AccessRevocationManagerImplTest, BlockListIsFull) {
+TEST_F(AccessRevocationManagerImplTest, BlockListOverflow) {
+  EXPECT_CALL(config_store_, LoadSettings("black_list")).WillOnce(Return(""));
+  manager_.reset(new AccessRevocationManagerImpl{&config_store_, 10, &clock_});
+
   EXPECT_CALL(config_store_, SaveSettings("black_list", _, _))
       .WillRepeatedly(testing::WithArgs<1, 2>(testing::Invoke(
           [](const std::string& json, const DoneCallback& callback) {
             if (!callback.is_null())
               callback.Run(nullptr);
           })));
-  for (size_t i = manager_->GetSize(); i < manager_->GetCapacity(); ++i) {
-    manager_->Block(
-        {{99, static_cast<uint8_t>(i / 256), static_cast<uint8_t>(i % 256)},
-         {8, 8, 8},
-         base::Time::FromTimeT(1419970000),
-         base::Time::FromTimeT(1419990000)},
-        {});
-    EXPECT_EQ(i + 1, manager_->GetSize());
+
+  EXPECT_EQ(0u, manager_->GetSize());
+
+  // Trigger overflow several times.
+  for (size_t i = 0; i < manager_->GetCapacity() + 3; ++i) {
+    bool callback_called = false;
+    manager_->Block({{99, static_cast<uint8_t>(i), static_cast<uint8_t>(i)},
+                     {8, 8, 8},
+                     base::Time::FromTimeT(1419970000 + i),
+                     base::Time::FromTimeT(1419990000)},
+                    base::Bind([&callback_called](ErrorPtr error) {
+                      callback_called = true;
+                      EXPECT_FALSE(error);
+                    }));
+    EXPECT_TRUE(callback_called);
   }
-  manager_->Block({{99},
-                   {8, 8, 8},
-                   base::Time::FromTimeT(1419970000),
-                   base::Time::FromTimeT(1419990000)},
-                  base::Bind([](ErrorPtr error) {
-                    EXPECT_TRUE(error->HasError("blacklist_is_full"));
-                  }));
+  EXPECT_EQ(manager_->GetCapacity(), manager_->GetSize());
+
+  // We didn't block these ids, so we can use this to check if all_blocking
+  // issue is set for correct revocation time.
+  EXPECT_TRUE(manager_->IsBlocked({1}, {2}, base::Time::FromTimeT(1419970003)));
+  EXPECT_FALSE(
+      manager_->IsBlocked({1}, {2}, base::Time::FromTimeT(1419970004)));
+
+  // Check if all blocking rules still work.
+  for (size_t i = 0; i < manager_->GetCapacity() + 3; ++i) {
+    EXPECT_TRUE(manager_->IsBlocked(
+        {99, static_cast<uint8_t>(i), static_cast<uint8_t>(i)}, {8, 8, 8},
+        base::Time::FromTimeT(1419970000 + i)));
+  }
 }
 
 TEST_F(AccessRevocationManagerImplTest, IsBlockedIdsNotMacth) {