diff --git a/pw_kvs/key_value_store.cc b/pw_kvs/key_value_store.cc
index 1801dc3..7c83eca 100644
--- a/pw_kvs/key_value_store.cc
+++ b/pw_kvs/key_value_store.cc
@@ -202,6 +202,12 @@
   return Status::OK;
 }
 
+Status KeyValueStore::RelocateEntry(KeyMapEntry& entry) {
+  // TODO: implement me
+  (void)entry;
+  return Status::UNIMPLEMENTED;
+}
+
 // Find either an existing sector with enough space, or an empty sector.
 // Maintains the invariant that there is always at least 1 empty sector.
 KeyValueStore::SectorMapEntry* KeyValueStore::FindSectorWithSpace(size_t size) {
@@ -243,17 +249,49 @@
   return Status::RESOURCE_EXHAUSTED;
 }
 
+KeyValueStore::SectorMapEntry* KeyValueStore::FindSectorToGarbageCollect() {
+  SectorMapEntry* sector_candidate = nullptr;
+  size_t candidate_bytes = 0;
+
+  // Step 1: Try to find a sectors with stale keys and no valid keys (no
+  // relocation needed). If any such sectors are found, use the sector with the
+  // most reclaimable bytes.
+  for (auto& sector : sector_map_) {
+    if ((sector.valid_bytes == 0) &&
+        (RecoverableBytes(sector) > candidate_bytes)) {
+      sector_candidate = &sector;
+      candidate_bytes = RecoverableBytes(sector);
+    }
+  }
+
+  // Step 2: If step 1 yields no sectors, just find the sector with the most
+  // reclaimable bytes.
+  if (sector_candidate == nullptr) {
+    for (auto& sector : sector_map_) {
+      if (RecoverableBytes(sector) > candidate_bytes) {
+        sector_candidate = &sector;
+        candidate_bytes = RecoverableBytes(sector);
+      }
+    }
+  }
+
+  return sector_candidate;
+}
+
 Status KeyValueStore::GarbageCollectOneSector(SectorMapEntry** sector) {
-  // TODO: THIS NEEDS WORK
-  (void)sector;
+  // Step 1: Find the sector to garbage collect
   SectorMapEntry* sector_to_gc = FindSectorToGarbageCollect();
 
-  const Address sector_base = SectorBaseAddress(sector_to_gc);
-  const Address sector_end = sector_base + partition_.sector_size_bytes();
+  if (sector_to_gc == nullptr) {
+    return Status::RESOURCE_EXHAUSTED;
+  }
 
-  for (auto entry : entries()) {
-    if ((entry.address >= sector_base) && (entry.address < sector_end)) {
-      // RelocateEntry(entry);
+  // Step 2: Move any valid entries in the GC sector to other sectors
+  if (sector_to_gc->valid_bytes != 0) {
+    for (auto& entry : entries()) {
+      if (AddressInSector(*sector_to_gc, entry.address)) {
+        TRY(RelocateEntry(entry));
+      }
     }
   }
 
@@ -261,12 +299,13 @@
     return Status::INTERNAL;
   }
 
-  return Status::OK;
-}
+  // Step 3: Reinitialize the sector
+  sector_to_gc->tail_free_bytes = 0;
+  TRY(partition_.Erase(SectorBaseAddress(sector_to_gc), 1));
+  sector_to_gc->tail_free_bytes = partition_.sector_size_bytes();
 
-KeyValueStore::SectorMapEntry* KeyValueStore::FindSectorToGarbageCollect() {
-  // TODO: implement me
-  return nullptr;
+  *sector = sector_to_gc;
+  return Status::OK;
 }
 
 Status KeyValueStore::AppendEntry(SectorMapEntry* sector,
@@ -321,10 +360,4 @@
   return checksum.state();
 }
 
-Status KeyValueStore::RelocateEntry(KeyMapEntry* entry) {
-  // TODO: implement me
-  (void)entry;
-  return Status::UNIMPLEMENTED;
-}
-
 }  // namespace pw::kvs
diff --git a/pw_kvs/public/pw_kvs/flash_memory.h b/pw_kvs/public/pw_kvs/flash_memory.h
index 5495141..06a5148 100644
--- a/pw_kvs/public/pw_kvs/flash_memory.h
+++ b/pw_kvs/public/pw_kvs/flash_memory.h
@@ -189,15 +189,13 @@
                                 size_t len,
                                 bool* is_erased);
 
-  constexpr uint32_t sector_size_bytes() const {
+  // Overridden by derived classes. The reported sector size is space available
+  // to users of FlashPartition. It accounts for space reserved in the sector
+  // for FlashPartition to store metadata.
+  virtual uint32_t sector_size_bytes() const {
     return flash_.sector_size_bytes();
   }
 
-  // Overridden by base classes which store metadata at the start of a sector.
-  virtual uint32_t sector_available_size_bytes() const {
-    return sector_size_bytes();
-  }
-
   size_t size_bytes() const { return sector_count() * sector_size_bytes(); }
 
   virtual size_t alignment_bytes() const { return flash_.alignment_bytes(); }
diff --git a/pw_kvs/public/pw_kvs/key_value_store.h b/pw_kvs/public/pw_kvs/key_value_store.h
index 115bea0..f399629 100644
--- a/pw_kvs/public/pw_kvs/key_value_store.h
+++ b/pw_kvs/public/pw_kvs/key_value_store.h
@@ -248,6 +248,8 @@
 
   Status WriteEntryForNewKey(std::string_view key, span<const std::byte> value);
 
+  Status RelocateEntry(KeyMapEntry& entry);
+
   SectorMapEntry* FindSectorWithSpace(size_t size);
 
   Status FindOrRecoverSectorWithSpace(SectorMapEntry** sector, size_t size);
@@ -268,10 +270,15 @@
       std::string_view key,
       span<const std::byte> value) const;
 
-  Status RelocateEntry(KeyMapEntry* entry);
+  bool AddressInSector(const SectorMapEntry& sector, Address address) const {
+    const Address sector_base = SectorBaseAddress(&sector);
+    const Address sector_end = sector_base + partition_.sector_size_bytes();
+
+    return ((address >= sector_base) && (address < sector_end));
+  }
 
   bool SectorEmpty(const SectorMapEntry& sector) const {
-    return (sector.tail_free_bytes == partition_.sector_available_size_bytes());
+    return (sector.tail_free_bytes == partition_.sector_size_bytes());
   }
 
   size_t RecoverableBytes(const SectorMapEntry& sector) {
@@ -279,7 +286,7 @@
            sector.tail_free_bytes;
   }
 
-  Address SectorBaseAddress(SectorMapEntry* sector) const {
+  Address SectorBaseAddress(const SectorMapEntry* sector) const {
     return (sector - sector_map_.data()) * partition_.sector_size_bytes();
   }