diff --git a/pw_kvs/key_value_store.cc b/pw_kvs/key_value_store.cc
index 1f3737e..539be83 100644
--- a/pw_kvs/key_value_store.cc
+++ b/pw_kvs/key_value_store.cc
@@ -83,6 +83,8 @@
   if (!error_detected_) {
     initialized_ = InitializationState::kReady;
   } else {
+    initialized_ = InitializationState::kNeedsMaintenance;
+
     if (options_.recovery != ErrorRecovery::kManual) {
       size_t pre_fix_redundancy_errors =
           error_stats_.missing_redundant_entries_recovered;
@@ -99,14 +101,11 @@
         initialized_ = InitializationState::kReady;
       } else if (recovery_status == Status::RESOURCE_EXHAUSTED) {
         WRN("KVS init: Unable to maintain required free sector");
-        initialized_ = InitializationState::kNeedsMaintenance;
       } else {
         WRN("KVS init: Corruption detected and unable repair");
-        initialized_ = InitializationState::kNeedsMaintenance;
       }
     } else {
       WRN("KVS init: Corruption detected, no repair attempted due to options");
-      initialized_ = InitializationState::kNeedsMaintenance;
     }
   }
 
@@ -874,20 +873,24 @@
   return Status::OK;
 }
 
-Status KeyValueStore::GarbageCollect(span<const Address> reserved_addresses) {
+Status KeyValueStore::PartialMaintenance() {
   if (initialized_ == InitializationState::kNotInitialized) {
     return Status::FAILED_PRECONDITION;
   }
 
-  DBG("Garbage Collect a single sector");
-  for (Address address : reserved_addresses) {
-    DBG("   Avoid address %u", unsigned(address));
-  }
-
+  CheckForErrors();
   // Do automatic repair, if KVS options allow for it.
   if (error_detected_ && options_.recovery != ErrorRecovery::kManual) {
     TRY(Repair());
   }
+  return GarbageCollect(span<const Address>());
+}
+
+Status KeyValueStore::GarbageCollect(span<const Address> reserved_addresses) {
+  DBG("Garbage Collect a single sector");
+  for (Address address : reserved_addresses) {
+    DBG("   Avoid address %u", unsigned(address));
+  }
 
   // Step 1: Find the sector to garbage collect
   SectorDescriptor* sector_to_gc =
@@ -993,17 +996,13 @@
 
 // Add any missing redundant entries/copies for a key.
 Status KeyValueStore::AddRedundantEntries(EntryMetadata& metadata) {
-  SectorDescriptor* new_sector;
-
   Entry entry;
-
   TRY(ReadEntry(metadata, entry));
   TRY(entry.VerifyChecksumInFlash());
 
-  for (size_t i = metadata.addresses().size();
-       metadata.addresses().size() < redundancy();
-       i++) {
-    TRY(sectors_.FindSpace(&new_sector, entry.size(), metadata.addresses()));
+  while (metadata.addresses().size() < redundancy()) {
+    SectorDescriptor* new_sector;
+    TRY(GetSectorForWrite(&new_sector, entry.size(), metadata.addresses()));
 
     Address new_address = sectors_.NextWritableAddress(*new_sector);
     TRY(CopyEntryToSector(entry, new_sector, new_address));
diff --git a/pw_kvs/key_value_store_binary_format_test.cc b/pw_kvs/key_value_store_binary_format_test.cc
index b900d44..f2f8308 100644
--- a/pw_kvs/key_value_store_binary_format_test.cc
+++ b/pw_kvs/key_value_store_binary_format_test.cc
@@ -960,5 +960,101 @@
   EXPECT_EQ(stats.missing_redundant_entries_recovered, 4u);
 }
 
+class InitializedLazyRecoveryKvs : public ::testing::Test {
+ protected:
+  static constexpr auto kInitialContents =
+      AsBytes(kEntry1, kEntry2, kEntry3, kEntry4);
+
+  InitializedLazyRecoveryKvs()
+      : flash_(internal::Entry::kMinAlignmentBytes),
+        partition_(&flash_),
+        kvs_(&partition_,
+             {.magic = kMagic, .checksum = &checksum},
+             kRecoveryLazyGcOptions) {
+    partition_.Erase();
+    std::memcpy(flash_.buffer().data(),
+                kInitialContents.data(),
+                kInitialContents.size());
+
+    EXPECT_EQ(Status::OK, kvs_.Init());
+  }
+
+  FakeFlashBuffer<512, 8> flash_;
+  FlashPartition partition_;
+  KeyValueStoreBuffer<kMaxEntries, kMaxUsableSectors> kvs_;
+};
+
+// Block of data to use for entry value. Sized to 470 so the total entry results
+// in the 512 byte sector having 16 bytes remaining.
+constexpr uint8_t test_data[470] = {1, 2, 3, 4, 5, 6};
+
+// Test a KVS with a number of entries, several sectors that are nearly full
+// of stale (reclaimable) space, and not enough writable (free) space to add a
+// redundant copy for any of the entries. Tests that the add redundancy step of
+// repair is able to use garbage collection to free up space needed for the new
+// copies.
+TEST_F(InitializedLazyRecoveryKvs, AddRedundancyToKvsFullOfStaleData) {
+  // Verify the pre-initialized key are present in the KVS.
+  ASSERT_CONTAINS_ENTRY("key1", "value1");
+  ASSERT_CONTAINS_ENTRY("k2", "value2");
+  ASSERT_CONTAINS_ENTRY("k3y", "value3");
+  ASSERT_CONTAINS_ENTRY("4k", "value4");
+
+  EXPECT_EQ(false, kvs_.error_detected());
+
+  auto stats = kvs_.GetStorageStats();
+  EXPECT_EQ(stats.in_use_bytes, (128u * kvs_.redundancy()));
+  EXPECT_EQ(stats.reclaimable_bytes, 0u);
+  EXPECT_EQ(stats.writable_bytes, 7 * 512u - (128u * kvs_.redundancy()));
+  EXPECT_EQ(stats.corrupt_sectors_recovered, 0u);
+  EXPECT_EQ(stats.missing_redundant_entries_recovered, 0u);
+
+  // Add a near-sector size key entry to fill the KVS with a valid large entry
+  // and stale data.
+
+  EXPECT_EQ(Status::OK, kvs_.Put("big_key", test_data));
+  EXPECT_EQ(Status::OK, kvs_.Put("big_key", test_data));
+  EXPECT_EQ(Status::OK, kvs_.Put("big_key", test_data));
+  EXPECT_EQ(Status::OK, kvs_.Put("big_key", test_data));
+  EXPECT_EQ(Status::OK, kvs_.Put("big_key", test_data));
+  EXPECT_EQ(Status::OK, kvs_.Put("big_key", test_data));
+
+  // Instantiate a new KVS with redundancy of 2. This KVS should add an extra
+  // copy of each valid key as part of the init process. Because there is not
+  // enough writable space, the adding redundancy will need to garbage collect
+  // two sectors.
+  KeyValueStoreBuffer<kMaxEntries, kMaxUsableSectors, 2> local_kvs(
+      &partition_,
+      {.magic = kMagic, .checksum = &checksum},
+      kRecoveryLazyGcOptions);
+  ASSERT_EQ(Status::OK, local_kvs.Init());
+
+  // Verify no errors found in the new KVS and all the entries are present.
+  EXPECT_EQ(false, local_kvs.error_detected());
+  ASSERT_KVS_CONTAINS_ENTRY(local_kvs, "key1", "value1");
+  ASSERT_KVS_CONTAINS_ENTRY(local_kvs, "k2", "value2");
+  ASSERT_KVS_CONTAINS_ENTRY(local_kvs, "k3y", "value3");
+  ASSERT_KVS_CONTAINS_ENTRY(local_kvs, "4k", "value4");
+  StatusWithSize big_key_size = local_kvs.ValueSize("big_key");
+  EXPECT_EQ(Status::OK, big_key_size.status());
+  EXPECT_EQ(sizeof(test_data), big_key_size.size());
+
+  // Verify that storage stats of the new redundant KVS match expected values.
+  stats = local_kvs.GetStorageStats();
+
+  // Expected in-use bytes is size of (pre-init keys + big key) * redundancy.
+  EXPECT_EQ(stats.in_use_bytes, ((128u + 496u) * local_kvs.redundancy()));
+
+  // Expected reclaimable space is number of stale entries remaining for big_key
+  // (3 after GC to add redundancy) * total sizeof big_key entry (496 bytes).
+
+  EXPECT_EQ(stats.reclaimable_bytes, 496u * 3u);
+  // Expected writable bytes is total writable size (512 * 7) - valid bytes (in
+  // use) - reclaimable bytes.
+  EXPECT_EQ(stats.writable_bytes, 848u);
+  EXPECT_EQ(stats.corrupt_sectors_recovered, 0u);
+  EXPECT_EQ(stats.missing_redundant_entries_recovered, 0u);
+}
+
 }  // namespace
 }  // namespace pw::kvs
diff --git a/pw_kvs/public/pw_kvs/key_value_store.h b/pw_kvs/public/pw_kvs/key_value_store.h
index e8fde2c..4ca5102 100644
--- a/pw_kvs/public/pw_kvs/key_value_store.h
+++ b/pw_kvs/public/pw_kvs/key_value_store.h
@@ -188,10 +188,7 @@
   // recovery, will do any needed repairing of corruption. Does garbage
   // collection of part of the KVS, typically a single sector or similar unit
   // that makes sense for the KVS implementation.
-  Status PartialMaintenance() {
-    CheckForErrors();
-    return GarbageCollect(span<const Address>());
-  }
+  Status PartialMaintenance();
 
   void LogDebugInfo() const;