diff --git a/pw_kvs/BUILD b/pw_kvs/BUILD
index 82c4002..3a1680b 100644
--- a/pw_kvs/BUILD
+++ b/pw_kvs/BUILD
@@ -382,8 +382,8 @@
 )
 
 pw_cc_test(
-    name = "key_value_store_fuzz_test",
-    srcs = ["key_value_store_fuzz_test.cc"],
+    name = "key_value_store_put_test",
+    srcs = ["key_value_store_put_test.cc"],
     deps = [
         ":crc16",
         ":pw_kvs",
diff --git a/pw_kvs/BUILD.gn b/pw_kvs/BUILD.gn
index a8d84ab..e94ebaa 100644
--- a/pw_kvs/BUILD.gn
+++ b/pw_kvs/BUILD.gn
@@ -213,6 +213,19 @@
   sources = [ "key_value_store_initialized_test.cc" ]
 }
 
+pw_source_set("key_value_store_fuzz_test") {
+  deps = [
+    ":crc16",
+    ":flash_test_partition",
+    ":pw_kvs",
+    dir_pw_bytes,
+    dir_pw_checksum,
+    dir_pw_log,
+    dir_pw_unit_test,
+  ]
+  sources = [ "key_value_store_fuzz_test.cc" ]
+}
+
 pw_source_set("test_key_value_store_test") {
   deps = [
     ":pw_kvs",
@@ -248,9 +261,10 @@
     ":key_value_store_test",
     ":key_value_store_small_flash_test",
     ":key_value_store_64_alignment_flash_test",
+    ":key_value_store_fuzz_64_alignment_flash_test",
     ":key_value_store_256_alignment_flash_test",
     ":key_value_store_binary_format_test",
-    ":key_value_store_fuzz_test",
+    ":key_value_store_put_test",
     ":key_value_store_map_test",
     ":fake_flash_test_key_value_store_test",
     ":sectors_test",
@@ -350,6 +364,13 @@
   ]
 }
 
+pw_test("key_value_store_fuzz_64_alignment_flash_test") {
+  deps = [
+    ":fake_flash_64_aligned_partition",
+    ":key_value_store_fuzz_test",
+  ]
+}
+
 pw_test("key_value_store_256_alignment_flash_test") {
   deps = [
     ":fake_flash_256_aligned_partition",
@@ -368,14 +389,14 @@
   sources = [ "key_value_store_binary_format_test.cc" ]
 }
 
-pw_test("key_value_store_fuzz_test") {
+pw_test("key_value_store_put_test") {
   deps = [
     ":crc16",
     ":fake_flash",
     ":pw_kvs",
     ":test_partition",
   ]
-  sources = [ "key_value_store_fuzz_test.cc" ]
+  sources = [ "key_value_store_put_test.cc" ]
 }
 
 pw_test("fake_flash_test_key_value_store_test") {
diff --git a/pw_kvs/key_value_store_fuzz_test.cc b/pw_kvs/key_value_store_fuzz_test.cc
index 6a257d6..aaa7a34 100644
--- a/pw_kvs/key_value_store_fuzz_test.cc
+++ b/pw_kvs/key_value_store_fuzz_test.cc
@@ -1,4 +1,4 @@
-// Copyright 2020 The Pigweed Authors
+// Copyright 2021 The Pigweed Authors
 //
 // Licensed under the Apache License, Version 2.0 (the "License"); you may not
 // use this file except in compliance with the License. You may obtain a copy of
@@ -12,66 +12,96 @@
 // License for the specific language governing permissions and limitations under
 // the License.
 
+#include <array>
+#include <cstring>
+#include <span>
+
 #include "gtest/gtest.h"
+#include "pw_checksum/crc16_ccitt.h"
 #include "pw_kvs/crc16_checksum.h"
-#include "pw_kvs/fake_flash_memory.h"
-#include "pw_kvs/flash_partition_with_stats.h"
+#include "pw_kvs/flash_memory.h"
+#include "pw_kvs/flash_test_partition.h"
 #include "pw_kvs/key_value_store.h"
+#include "pw_log/log.h"
+#include "pw_status/status.h"
 
 namespace pw::kvs {
 namespace {
 
 using std::byte;
 
-#ifndef PW_KVS_FUZZ_ITERATIONS
-#define PW_KVS_FUZZ_ITERATIONS 2
-#endif  // PW_KVS_FUZZ_ITERATIONS
-constexpr int kFuzzIterations = PW_KVS_FUZZ_ITERATIONS;
-
 constexpr size_t kMaxEntries = 256;
-constexpr size_t kMaxUsableSectors = 256;
+constexpr size_t kMaxUsableSectors = 1024;
 
-// 4 x 4k sectors, 16 byte alignment
-FakeFlashMemoryBuffer<4 * 1024, 6> test_flash(16);
-
-FlashPartitionWithStatsBuffer<kMaxUsableSectors> test_partition(
-    &test_flash, 0, test_flash.sector_count());
+constexpr std::array<const char*, 3> keys{"TestKey1", "Key2", "TestKey3"};
 
 ChecksumCrc16 checksum;
+// For KVS magic value always use a random 32 bit integer rather than a
+// human readable 4 bytes. See pw_kvs/format.h for more information.
+constexpr EntryFormat default_format{.magic = 0x749c361e,
+                                     .checksum = &checksum};
+}  // namespace
 
-class EmptyInitializedKvs : public ::testing::Test {
- protected:
-  // For KVS magic value always use a random 32 bit integer rather than a
-  // human readable 4 bytes. See pw_kvs/format.h for more information.
-  EmptyInitializedKvs()
-      : kvs_(&test_partition, {.magic = 0x873a9b50, .checksum = &checksum}) {
-    test_partition.Erase(0, test_partition.sector_count());
-    ASSERT_EQ(OkStatus(), kvs_.Init());
+TEST(KvsFuzz, FuzzTest) {
+  FlashPartition& test_partition = FlashTestPartition();
+  test_partition.Erase();
+
+  KeyValueStoreBuffer<kMaxEntries, kMaxUsableSectors> kvs_(&test_partition,
+                                                           default_format);
+
+  ASSERT_EQ(OkStatus(), kvs_.Init());
+
+  if (test_partition.sector_size_bytes() < 4 * 1024 ||
+      test_partition.sector_count() < 4) {
+    PW_LOG_INFO("Sectors too small, skipping test.");
+    return;  // TODO: Test could be generalized
+  }
+  const char* key1 = "Buf1";
+  const char* key2 = "Buf2";
+  const size_t kLargestBufSize = 3 * 1024;
+  static byte buf1[kLargestBufSize];
+  static byte buf2[kLargestBufSize];
+  std::memset(buf1, 1, sizeof(buf1));
+  std::memset(buf2, 2, sizeof(buf2));
+
+  // Start with things in KVS
+  ASSERT_EQ(OkStatus(), kvs_.Put(key1, buf1));
+  ASSERT_EQ(OkStatus(), kvs_.Put(key2, buf2));
+  for (size_t j = 0; j < keys.size(); j++) {
+    ASSERT_EQ(OkStatus(), kvs_.Put(keys[j], j));
   }
 
-  KeyValueStoreBuffer<kMaxEntries, kMaxUsableSectors> kvs_;
-};
+  for (size_t i = 0; i < 100; i++) {
+    // Vary two sizes
+    size_t size1 = (kLargestBufSize) / (i + 1);
+    size_t size2 = (kLargestBufSize) / (100 - i);
+    for (size_t j = 0; j < 50; j++) {
+      // Rewrite a single key many times, can fill up a sector
+      ASSERT_EQ(OkStatus(), kvs_.Put("some_data", j));
+    }
+    // Delete and re-add everything
+    ASSERT_EQ(OkStatus(), kvs_.Delete(key1));
+    ASSERT_EQ(OkStatus(), kvs_.Put(key1, std::span(buf1, size1)));
+    ASSERT_EQ(OkStatus(), kvs_.Delete(key2));
+    ASSERT_EQ(OkStatus(), kvs_.Put(key2, std::span(buf2, size2)));
+    for (size_t j = 0; j < keys.size(); j++) {
+      ASSERT_EQ(OkStatus(), kvs_.Delete(keys[j]));
+      ASSERT_EQ(OkStatus(), kvs_.Put(keys[j], j));
+    }
 
-TEST_F(EmptyInitializedKvs, Put_VaryingKeysAndValues) {
-  char value[] =
-      "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"  // 52
-      "34567890123";  // 64 (with final \0);
-  static_assert(sizeof(value) == 64);
-
-  test_partition.ResetCounters();
-
-  for (int i = 0; i < kFuzzIterations; ++i) {
-    for (unsigned key_size = 1; key_size < sizeof(value); ++key_size) {
-      for (unsigned value_size = 0; value_size < sizeof(value); ++value_size) {
-        ASSERT_EQ(OkStatus(),
-                  kvs_.Put(std::string_view(value, key_size),
-                           std::as_bytes(std::span(value, value_size))));
-      }
+    // Re-enable and verify
+    ASSERT_EQ(OkStatus(), kvs_.Init());
+    static byte buf[4 * 1024];
+    ASSERT_EQ(OkStatus(), kvs_.Get(key1, std::span(buf, size1)).status());
+    ASSERT_EQ(std::memcmp(buf, buf1, size1), 0);
+    ASSERT_EQ(OkStatus(), kvs_.Get(key2, std::span(buf, size2)).status());
+    ASSERT_EQ(std::memcmp(buf2, buf2, size2), 0);
+    for (size_t j = 0; j < keys.size(); j++) {
+      size_t ret = 1000;
+      ASSERT_EQ(OkStatus(), kvs_.Get(keys[j], &ret));
+      ASSERT_EQ(ret, j);
     }
   }
-
-  test_partition.SaveStorageStats(kvs_, "fuzz Put_VaryingKeysAndValues");
 }
 
-}  // namespace
 }  // namespace pw::kvs
diff --git a/pw_kvs/key_value_store_initialized_test.cc b/pw_kvs/key_value_store_initialized_test.cc
index 9994fb6..1b1f820 100644
--- a/pw_kvs/key_value_store_initialized_test.cc
+++ b/pw_kvs/key_value_store_initialized_test.cc
@@ -36,7 +36,7 @@
 using std::byte;
 
 constexpr size_t kMaxEntries = 256;
-constexpr size_t kMaxUsableSectors = 256;
+constexpr size_t kMaxUsableSectors = 1024;
 
 FlashPartition& test_partition = FlashTestPartition();
 
@@ -408,60 +408,6 @@
   }
 }
 
-TEST_F(EmptyInitializedKvs, FuzzTest) {
-  if (test_partition.sector_size_bytes() < 4 * 1024 ||
-      test_partition.sector_count() < 4) {
-    PW_LOG_INFO("Sectors too small, skipping test.");
-    return;  // TODO: Test could be generalized
-  }
-  const char* key1 = "Buf1";
-  const char* key2 = "Buf2";
-  const size_t kLargestBufSize = 3 * 1024;
-  static byte buf1[kLargestBufSize];
-  static byte buf2[kLargestBufSize];
-  std::memset(buf1, 1, sizeof(buf1));
-  std::memset(buf2, 2, sizeof(buf2));
-
-  // Start with things in KVS
-  ASSERT_EQ(OkStatus(), kvs_.Put(key1, buf1));
-  ASSERT_EQ(OkStatus(), kvs_.Put(key2, buf2));
-  for (size_t j = 0; j < keys.size(); j++) {
-    ASSERT_EQ(OkStatus(), kvs_.Put(keys[j], j));
-  }
-
-  for (size_t i = 0; i < 100; i++) {
-    // Vary two sizes
-    size_t size1 = (kLargestBufSize) / (i + 1);
-    size_t size2 = (kLargestBufSize) / (100 - i);
-    for (size_t j = 0; j < 50; j++) {
-      // Rewrite a single key many times, can fill up a sector
-      ASSERT_EQ(OkStatus(), kvs_.Put("some_data", j));
-    }
-    // Delete and re-add everything
-    ASSERT_EQ(OkStatus(), kvs_.Delete(key1));
-    ASSERT_EQ(OkStatus(), kvs_.Put(key1, std::span(buf1, size1)));
-    ASSERT_EQ(OkStatus(), kvs_.Delete(key2));
-    ASSERT_EQ(OkStatus(), kvs_.Put(key2, std::span(buf2, size2)));
-    for (size_t j = 0; j < keys.size(); j++) {
-      ASSERT_EQ(OkStatus(), kvs_.Delete(keys[j]));
-      ASSERT_EQ(OkStatus(), kvs_.Put(keys[j], j));
-    }
-
-    // Re-enable and verify
-    ASSERT_EQ(OkStatus(), kvs_.Init());
-    static byte buf[4 * 1024];
-    ASSERT_EQ(OkStatus(), kvs_.Get(key1, std::span(buf, size1)).status());
-    ASSERT_EQ(std::memcmp(buf, buf1, size1), 0);
-    ASSERT_EQ(OkStatus(), kvs_.Get(key2, std::span(buf, size2)).status());
-    ASSERT_EQ(std::memcmp(buf2, buf2, size2), 0);
-    for (size_t j = 0; j < keys.size(); j++) {
-      size_t ret = 1000;
-      ASSERT_EQ(OkStatus(), kvs_.Get(keys[j], &ret));
-      ASSERT_EQ(ret, j);
-    }
-  }
-}
-
 TEST_F(EmptyInitializedKvs, Basic) {
   // Add some data
   uint8_t value1 = 0xDA;
diff --git a/pw_kvs/key_value_store_put_test.cc b/pw_kvs/key_value_store_put_test.cc
new file mode 100644
index 0000000..5c9c97c
--- /dev/null
+++ b/pw_kvs/key_value_store_put_test.cc
@@ -0,0 +1,77 @@
+// Copyright 2020 The Pigweed Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License"); you may not
+// use this file except in compliance with the License. You may obtain a copy of
+// the License at
+//
+//     https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+// License for the specific language governing permissions and limitations under
+// the License.
+
+#include "gtest/gtest.h"
+#include "pw_kvs/crc16_checksum.h"
+#include "pw_kvs/fake_flash_memory.h"
+#include "pw_kvs/flash_partition_with_stats.h"
+#include "pw_kvs/key_value_store.h"
+
+namespace pw::kvs {
+namespace {
+
+using std::byte;
+
+#ifndef PW_KVS_PUT_ITERATIONS
+#define PW_KVS_PUT_ITERATIONS 2
+#endif  // PW_KVS_PUT_ITERATIONS
+constexpr int kPutIterations = PW_KVS_PUT_ITERATIONS;
+
+constexpr size_t kMaxEntries = 256;
+constexpr size_t kMaxUsableSectors = 256;
+
+// 4 x 4k sectors, 16 byte alignment
+FakeFlashMemoryBuffer<4 * 1024, 6> test_flash(16);
+
+FlashPartitionWithStatsBuffer<kMaxUsableSectors> test_partition(
+    &test_flash, 0, test_flash.sector_count());
+
+ChecksumCrc16 checksum;
+
+class EmptyInitializedKvs : public ::testing::Test {
+ protected:
+  // For KVS magic value always use a random 32 bit integer rather than a
+  // human readable 4 bytes. See pw_kvs/format.h for more information.
+  EmptyInitializedKvs()
+      : kvs_(&test_partition, {.magic = 0x873a9b50, .checksum = &checksum}) {
+    test_partition.Erase(0, test_partition.sector_count());
+    ASSERT_EQ(OkStatus(), kvs_.Init());
+  }
+
+  KeyValueStoreBuffer<kMaxEntries, kMaxUsableSectors> kvs_;
+};
+
+TEST_F(EmptyInitializedKvs, Put_VaryingKeysAndValues) {
+  char value[] =
+      "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"  // 52
+      "34567890123";  // 64 (with final \0);
+  static_assert(sizeof(value) == 64);
+
+  test_partition.ResetCounters();
+
+  for (int i = 0; i < kPutIterations; ++i) {
+    for (unsigned key_size = 1; key_size < sizeof(value); ++key_size) {
+      for (unsigned value_size = 0; value_size < sizeof(value); ++value_size) {
+        ASSERT_EQ(OkStatus(),
+                  kvs_.Put(std::string_view(value, key_size),
+                           std::as_bytes(std::span(value, value_size))));
+      }
+    }
+  }
+
+  test_partition.SaveStorageStats(kvs_, "Put_VaryingKeysAndValues");
+}
+
+}  // namespace
+}  // namespace pw::kvs