diff --git a/pw_kvs/key_value_store.cc b/pw_kvs/key_value_store.cc
index 170ddf0..f3cb4a6 100644
--- a/pw_kvs/key_value_store.cc
+++ b/pw_kvs/key_value_store.cc
@@ -852,7 +852,9 @@
   if (error_detected_) {
     TRY(Repair());
   }
-  Status overall_status = UpdateEntriesToPrimaryFormat();
+  StatusWithSize update_status = UpdateEntriesToPrimaryFormat();
+  Status overall_status = update_status.status();
+
   // Make sure all the entries are on the primary format.
   if (!overall_status.ok()) {
     ERR("Failed to update all entries to the primary format");
@@ -860,6 +862,15 @@
 
   SectorDescriptor* sector = sectors_.last_new();
 
+  // Calculate number of bytes for the threshold.
+  size_t threshold_bytes =
+      (partition_.size_bytes() * kGcUsageThresholdPercentage) / 100;
+
+  // Is bytes in use over the threshold.
+  StorageStats stats = GetStorageStats();
+  bool over_usage_threshold = stats.in_use_bytes > threshold_bytes;
+  bool force_gc = over_usage_threshold || (update_status.size() > 0);
+
   // TODO: look in to making an iterator method for cycling through sectors
   // starting from last_new_sector_.
   Status gc_status;
@@ -869,7 +880,8 @@
       sector = sectors_.begin();
     }
 
-    if (sector->RecoverableBytes(partition_.sector_size_bytes()) > 0) {
+    if (sector->RecoverableBytes(partition_.sector_size_bytes()) > 0 &&
+        (force_gc || sector->valid_bytes() == 0)) {
       gc_status = GarbageCollectSector(*sector, {});
       if (!gc_status.ok()) {
         ERR("Failed to garbage collect all sectors");
@@ -964,10 +976,11 @@
   return Status::OK;
 }
 
-Status KeyValueStore::UpdateEntriesToPrimaryFormat() {
+StatusWithSize KeyValueStore::UpdateEntriesToPrimaryFormat() {
+  size_t entries_updated = 0;
   for (EntryMetadata& prior_metadata : entry_cache_) {
     Entry entry;
-    TRY(ReadEntry(prior_metadata, entry));
+    TRY_WITH_SIZE(ReadEntry(prior_metadata, entry));
     if (formats_.primary().magic == entry.magic()) {
       // Ignore entries that are already on the primary format.
       continue;
@@ -979,17 +992,20 @@
         unsigned(entry.magic()),
         unsigned(formats_.primary().magic));
 
+    entries_updated++;
+
     last_transaction_id_ += 1;
-    TRY(entry.Update(formats_.primary(), last_transaction_id_));
+    TRY_WITH_SIZE(entry.Update(formats_.primary(), last_transaction_id_));
 
     // List of addresses for sectors with space for this entry.
     Address* reserved_addresses = entry_cache_.TempReservedAddressesForWrite();
 
     // Find addresses to write the entry to. This may involve garbage collecting
     // one or more sectors.
-    TRY(GetAddressesForWrite(reserved_addresses, entry.size()));
+    TRY_WITH_SIZE(GetAddressesForWrite(reserved_addresses, entry.size()));
 
-    TRY(CopyEntryToSector(entry,
+    TRY_WITH_SIZE(
+        CopyEntryToSector(entry,
                           &sectors_.FromAddress(reserved_addresses[0]),
                           reserved_addresses[0]));
 
@@ -1001,13 +1017,15 @@
     // Write the additional copies of the entry, if redundancy is greater
     // than 1.
     for (size_t i = 1; i < redundancy(); ++i) {
-      TRY(CopyEntryToSector(entry,
+      TRY_WITH_SIZE(
+          CopyEntryToSector(entry,
                             &sectors_.FromAddress(reserved_addresses[i]),
                             reserved_addresses[i]));
       new_metadata.AddNewAddress(reserved_addresses[i]);
     }
   }
-  return Status::OK;
+
+  return StatusWithSize(entries_updated);
 }
 
 // Add any missing redundant entries/copies for a key.
diff --git a/pw_kvs/key_value_store_map_test.cc b/pw_kvs/key_value_store_map_test.cc
index e2d8f68..5bd8535 100644
--- a/pw_kvs/key_value_store_map_test.cc
+++ b/pw_kvs/key_value_store_map_test.cc
@@ -321,8 +321,12 @@
     StartOperation("GCFull");
     Status status = kvs_.FullMaintenance();
     EXPECT_EQ(Status::OK, status);
+
     KeyValueStore::StorageStats post_stats = kvs_.GetStorageStats();
-    EXPECT_EQ(post_stats.reclaimable_bytes, 0U);
+    if (post_stats.in_use_bytes > ((partition_.size_bytes() * 70) / 100)) {
+      EXPECT_EQ(post_stats.reclaimable_bytes, 0U);
+    }
+
     FinishOperation("GCFull", status);
   }
 
diff --git a/pw_kvs/public/pw_kvs/key_value_store.h b/pw_kvs/public/pw_kvs/key_value_store.h
index 4ca5102..061b512 100644
--- a/pw_kvs/public/pw_kvs/key_value_store.h
+++ b/pw_kvs/public/pw_kvs/key_value_store.h
@@ -443,7 +443,9 @@
 
   // Ensure that all entries are on the primary (first) format. Entries that are
   // not on the primary format are rewritten.
-  Status UpdateEntriesToPrimaryFormat();
+  //
+  // Return: status + number of entries updated.
+  StatusWithSize UpdateEntriesToPrimaryFormat();
 
   Status AddRedundantEntries(EntryMetadata& metadata);
 
@@ -477,6 +479,13 @@
 
   Options options_;
 
+  // Threshold value for when to garbage collect all stale data. Above the
+  // threshold, GC all reclaimable bytes regardless of if valid data is in
+  // sector. Below the threshold, only GC sectors with reclaimable bytes and no
+  // valid bytes. The threshold is based on the portion of KVS capacity used by
+  // valid bytes.
+  static constexpr size_t kGcUsageThresholdPercentage = 70;
+
   enum class InitializationState {
     // KVS Init() has not been called and KVS is not usable.
     kNotInitialized,