diff --git a/quic/core/packet_number_indexed_queue.h b/quic/core/packet_number_indexed_queue.h
index fd2ad73..a087022 100644
--- a/quic/core/packet_number_indexed_queue.h
+++ b/quic/core/packet_number_indexed_queue.h
@@ -63,6 +63,8 @@
   bool Remove(QuicPacketNumber packet_number, Function f);
 
   // Remove up to, but not including |packet_number|.
+  // Unused slots in the front are also removed, which means when the function
+  // returns, |first_packet()| can be larger than |packet_number|.
   void RemoveUpTo(QuicPacketNumber packet_number);
 
   bool IsEmpty() const { return number_of_present_entries_ == 0; }
@@ -209,9 +211,7 @@
     entries_.pop_front();
     first_packet_++;
   }
-  if (entries_.empty()) {
-    first_packet_.Clear();
-  }
+  Cleanup();
 }
 
 template <typename T>
diff --git a/quic/core/packet_number_indexed_queue_test.cc b/quic/core/packet_number_indexed_queue_test.cc
index e23df99..5f6b09c 100644
--- a/quic/core/packet_number_indexed_queue_test.cc
+++ b/quic/core/packet_number_indexed_queue_test.cc
@@ -178,8 +178,10 @@
   EXPECT_EQ(QuicPacketNumber(1001u), queue_.first_packet());
   EXPECT_EQ(2u, queue_.number_of_present_entries());
 
+  // Remove up to 1100, since [1100, 2001) are !present, they should be cleaned
+  // up from the front.
   queue_.RemoveUpTo(QuicPacketNumber(1100));
-  EXPECT_EQ(QuicPacketNumber(1100u), queue_.first_packet());
+  EXPECT_EQ(QuicPacketNumber(2001u), queue_.first_packet());
   EXPECT_EQ(1u, queue_.number_of_present_entries());
 
   queue_.RemoveUpTo(QuicPacketNumber(2001));