diff --git a/pw_kvs/BUILD b/pw_kvs/BUILD
index 571e44f..218d199 100644
--- a/pw_kvs/BUILD
+++ b/pw_kvs/BUILD
@@ -29,6 +29,7 @@
         "checksum.cc",
         "entry.cc",
         "flash_memory.cc",
+        "format.cc",
         "key_value_store.cc",
         "public/pw_kvs/internal/entry.h",
         "public/pw_kvs/internal/hash.h",
diff --git a/pw_kvs/BUILD.gn b/pw_kvs/BUILD.gn
index b191dba..d8396b5 100644
--- a/pw_kvs/BUILD.gn
+++ b/pw_kvs/BUILD.gn
@@ -34,6 +34,7 @@
     "checksum.cc",
     "entry.cc",
     "flash_memory.cc",
+    "format.cc",
     "key_value_store.cc",
     "public/pw_kvs/internal/entry.h",
     "public/pw_kvs/internal/hash.h",
diff --git a/pw_kvs/entry.cc b/pw_kvs/entry.cc
index 894b2ce..2c19fae 100644
--- a/pw_kvs/entry.cc
+++ b/pw_kvs/entry.cc
@@ -25,7 +25,10 @@
 using std::byte;
 using std::string_view;
 
-Status Entry::Read(FlashPartition& partition, Address address, Entry* entry) {
+Status Entry::Read(FlashPartition& partition,
+                   Address address,
+                   const internal::EntryFormats& formats,
+                   Entry* entry) {
   EntryHeader header;
   TRY(partition.Read(address, sizeof(header), &header));
 
@@ -36,7 +39,15 @@
     return Status::DATA_LOSS;
   }
 
-  *entry = Entry(&partition, address, header);
+  const EntryFormat* format = formats.Find(header.magic);
+  if (format == nullptr) {
+    PW_LOG_ERROR("Found corrupt magic: %" PRIx32 " at address %zx",
+                 header.magic,
+                 size_t(address));
+    return Status::DATA_LOSS;
+  }
+
+  *entry = Entry(&partition, address, *format, header);
   return Status::OK;
 }
 
@@ -61,6 +72,7 @@
              uint32_t transaction_id)
     : Entry(&partition,
             address,
+            format,
             {.magic = format.magic,
              .checksum = 0,
              .alignment_units =
@@ -68,8 +80,8 @@
              .key_length_bytes = static_cast<uint8_t>(key.size()),
              .value_size_bytes = value_size_bytes,
              .transaction_id = transaction_id}) {
-  if (format.checksum != nullptr) {
-    span<const byte> checksum = CalculateChecksum(format.checksum, key, value);
+  if (checksum_ != nullptr) {
+    span<const byte> checksum = CalculateChecksum(key, value);
     std::memcpy(&header_.checksum,
                 checksum.data(),
                 std::min(checksum.size(), sizeof(header_.checksum)));
@@ -104,17 +116,15 @@
   return StatusWithSize(read_size);
 }
 
-Status Entry::VerifyChecksum(ChecksumAlgorithm* algorithm,
-                             string_view key,
-                             span<const byte> value) const {
-  if (algorithm == nullptr) {
+Status Entry::VerifyChecksum(string_view key, span<const byte> value) const {
+  if (checksum_ == nullptr) {
     return checksum() == 0 ? Status::OK : Status::DATA_LOSS;
   }
-  CalculateChecksum(algorithm, key, value);
-  return algorithm->Verify(checksum_bytes());
+  CalculateChecksum(key, value);
+  return checksum_->Verify(checksum_bytes());
 }
 
-Status Entry::VerifyChecksumInFlash(ChecksumAlgorithm* algorithm) const {
+Status Entry::VerifyChecksumInFlash() const {
   // Read the entire entry piece-by-piece into a small buffer. If the entry is
   // 32 B or less, only one read is required.
   union {
@@ -137,18 +147,18 @@
     return Status::DATA_LOSS;
   }
 
-  if (algorithm == nullptr) {
+  if (checksum_ == nullptr) {
     return checksum() == 0 ? Status::OK : Status::DATA_LOSS;
   }
 
   // The checksum is calculated as if the header's checksum field were 0.
   header_to_verify.checksum = 0;
 
-  algorithm->Reset();
+  checksum_->Reset();
 
   while (true) {
     // Add the chunk in the buffer to the checksum.
-    algorithm->Update(buffer, read_size);
+    checksum_->Update(buffer, read_size);
 
     bytes_to_read -= read_size;
     if (bytes_to_read == 0u) {
@@ -161,8 +171,8 @@
     TRY(partition().Read(read_address, read_size, buffer));
   }
 
-  algorithm->Finish();
-  return algorithm->Verify(checksum_bytes());
+  checksum_->Finish();
+  return checksum_->Verify(checksum_bytes());
 }
 
 void Entry::DebugLog() {
@@ -176,18 +186,17 @@
   PW_LOG_DEBUG("   Alignment    = 0x%zx", size_t(alignment_bytes()));
 }
 
-span<const byte> Entry::CalculateChecksum(ChecksumAlgorithm* algorithm,
-                                          const string_view key,
+span<const byte> Entry::CalculateChecksum(const string_view key,
                                           span<const byte> value) const {
-  algorithm->Reset();
+  checksum_->Reset();
 
   {
     EntryHeader header_for_checksum = header_;
     header_for_checksum.checksum = 0;
 
-    algorithm->Update(&header_for_checksum, sizeof(header_for_checksum));
-    algorithm->Update(as_bytes(span(key)));
-    algorithm->Update(value);
+    checksum_->Update(&header_for_checksum, sizeof(header_for_checksum));
+    checksum_->Update(as_bytes(span(key)));
+    checksum_->Update(value);
   }
 
   // Update the checksum with 0s to pad the entry to its alignment boundary.
@@ -196,11 +205,11 @@
 
   while (padding_to_add > 0u) {
     const size_t chunk_size = std::min(padding_to_add, sizeof(padding));
-    algorithm->Update(padding, chunk_size);
+    checksum_->Update(padding, chunk_size);
     padding_to_add -= chunk_size;
   }
 
-  return algorithm->Finish();
+  return checksum_->Finish();
 }
 
 }  // namespace pw::kvs::internal
diff --git a/pw_kvs/entry_test.cc b/pw_kvs/entry_test.cc
index 64b1718..7d8a9c8 100644
--- a/pw_kvs/entry_test.cc
+++ b/pw_kvs/entry_test.cc
@@ -43,6 +43,7 @@
     for (size_t value : {size_t(0), align - 1, align, align + 1, 2 * align}) {
       Entry entry =
           Entry::Valid(partition, 0, kFormat, "k", {nullptr, value}, 0);
+
       ASSERT_EQ(AlignUp(sizeof(EntryHeader) + 1 /* key */ + value, align),
                 entry.size());
     }
@@ -77,8 +78,10 @@
   EXPECT_EQ(entry.transaction_id(), 123u);
 }
 
+constexpr uint32_t kMagicWithChecksum = 0x600df00d;
+
 constexpr auto kHeader1 = ByteStr(
-    "\x0d\xf0\x0d\x60"  // magic
+    "\x0d\xf0\x0d\x60"  // magic (600df00d)
     "\xC5\x65\x00\x00"  // checksum (CRC16)
     "\x01"              // alignment
     "\x05"              // key length
@@ -93,10 +96,14 @@
 constexpr auto kEntry1 = AsBytes(kHeader1, kKey1, kValue1, kPadding1);
 static_assert(kEntry1.size() == 32);
 
+ChecksumCrc16 checksum;
+constexpr EntryFormat kFormatWithChecksum{kMagicWithChecksum, &checksum};
+constexpr internal::EntryFormats kFormats(kFormatWithChecksum);
+
 class ValidEntryInFlash : public ::testing::Test {
  protected:
   ValidEntryInFlash() : flash_(kEntry1), partition_(&flash_) {
-    EXPECT_EQ(Status::OK, Entry::Read(partition_, 0, &entry_));
+    EXPECT_EQ(Status::OK, Entry::Read(partition_, 0, kFormats, &entry_));
   }
 
   FakeFlashBuffer<1024, 4> flash_;
@@ -105,13 +112,12 @@
 };
 
 TEST_F(ValidEntryInFlash, PassesChecksumVerification) {
-  ChecksumCrc16 checksum;
-  EXPECT_EQ(Status::OK, entry_.VerifyChecksumInFlash(&checksum));
-  EXPECT_EQ(Status::OK, entry_.VerifyChecksum(&checksum, "key45", kValue1));
+  EXPECT_EQ(Status::OK, entry_.VerifyChecksumInFlash());
+  EXPECT_EQ(Status::OK, entry_.VerifyChecksum("key45", kValue1));
 }
 
 TEST_F(ValidEntryInFlash, HeaderContents) {
-  EXPECT_EQ(entry_.magic(), 0x600DF00Du);
+  EXPECT_EQ(entry_.magic(), kMagicWithChecksum);
   EXPECT_EQ(entry_.key_length(), 5u);
   EXPECT_EQ(entry_.value_size(), 6u);
   EXPECT_EQ(entry_.transaction_id(), 0x96979899u);
@@ -187,11 +193,9 @@
 TEST(ValidEntry, Write) {
   FakeFlashBuffer<1024, 4> flash;
   FlashPartition partition(&flash, 0, flash.sector_count(), 32);
-  ChecksumCrc16 checksum;
-  const EntryFormat format{0x600DF00Du, &checksum};
 
-  Entry entry =
-      Entry::Valid(partition, 53, format, "key45", kValue1, 0x96979899u);
+  Entry entry = Entry::Valid(
+      partition, 53, kFormatWithChecksum, "key45", kValue1, 0x96979899u);
 
   auto result = entry.Write("key45", kValue1);
   EXPECT_EQ(Status::OK, result.status());
@@ -215,7 +219,7 @@
  protected:
   TombstoneEntryInFlash()
       : flash_(AsBytes(kHeader2, kKeyAndPadding2)), partition_(&flash_) {
-    EXPECT_EQ(Status::OK, Entry::Read(partition_, 0, &entry_));
+    EXPECT_EQ(Status::OK, Entry::Read(partition_, 0, kFormats, &entry_));
   }
 
   FakeFlashBuffer<1024, 4> flash_;
@@ -224,13 +228,12 @@
 };
 
 TEST_F(TombstoneEntryInFlash, PassesChecksumVerification) {
-  ChecksumCrc16 checksum;
-  EXPECT_EQ(Status::OK, entry_.VerifyChecksumInFlash(&checksum));
-  EXPECT_EQ(Status::OK, entry_.VerifyChecksum(&checksum, "K", {}));
+  EXPECT_EQ(Status::OK, entry_.VerifyChecksumInFlash());
+  EXPECT_EQ(Status::OK, entry_.VerifyChecksum("K", {}));
 }
 
 TEST_F(TombstoneEntryInFlash, HeaderContents) {
-  EXPECT_EQ(entry_.magic(), 0x600DF00Du);
+  EXPECT_EQ(entry_.magic(), kMagicWithChecksum);
   EXPECT_EQ(entry_.key_length(), 1u);
   EXPECT_EQ(entry_.value_size(), 0u);
   EXPECT_EQ(entry_.transaction_id(), 0x03020100u);
@@ -258,9 +261,9 @@
   FakeFlashBuffer<1024, 4> flash;
   FlashPartition partition(&flash);
   ChecksumCrc16 checksum;
-  const EntryFormat format{0x600DF00Du, &checksum};
 
-  Entry entry = Entry::Tombstone(partition, 16, format, "K", 0x03020100);
+  Entry entry =
+      Entry::Tombstone(partition, 16, kFormatWithChecksum, "K", 0x03020100);
 
   auto result = entry.Write("K", {});
   EXPECT_EQ(Status::OK, result.status());
@@ -275,15 +278,19 @@
   FakeFlashBuffer<1024, 4> flash(kEntry1);
   FlashPartition partition(&flash);
   Entry entry;
-  ASSERT_EQ(Status::OK, Entry::Read(partition, 0, &entry));
 
-  EXPECT_EQ(Status::DATA_LOSS, entry.VerifyChecksumInFlash(nullptr));
-  EXPECT_EQ(Status::DATA_LOSS, entry.VerifyChecksum(nullptr, {}, {}));
+  const EntryFormat format{kMagicWithChecksum, nullptr};
+  const internal::EntryFormats formats(format);
+
+  ASSERT_EQ(Status::OK, Entry::Read(partition, 0, formats, &entry));
+
+  EXPECT_EQ(Status::DATA_LOSS, entry.VerifyChecksumInFlash());
+  EXPECT_EQ(Status::DATA_LOSS, entry.VerifyChecksum({}, {}));
 
   std::memset(&flash.buffer()[4], 0, 4);  // set the checksum field to 0
-  ASSERT_EQ(Status::OK, Entry::Read(partition, 0, &entry));
-  EXPECT_EQ(Status::OK, entry.VerifyChecksumInFlash(nullptr));
-  EXPECT_EQ(Status::OK, entry.VerifyChecksum(nullptr, {}, {}));
+  ASSERT_EQ(Status::OK, Entry::Read(partition, 0, formats, &entry));
+  EXPECT_EQ(Status::OK, entry.VerifyChecksumInFlash());
+  EXPECT_EQ(Status::OK, entry.VerifyChecksum({}, {}));
 }
 
 TEST(Entry, Checksum_ChecksPadding) {
@@ -291,17 +298,16 @@
       AsBytes(kHeader1, kKey1, kValue1, ByteStr("\0\0\0\0\1")));
   FlashPartition partition(&flash);
   Entry entry;
-  ASSERT_EQ(Status::OK, Entry::Read(partition, 0, &entry));
+  ASSERT_EQ(Status::OK, Entry::Read(partition, 0, kFormats, &entry));
 
   // Last byte in padding is a 1; should fail.
-  ChecksumCrc16 checksum;
-  EXPECT_EQ(Status::DATA_LOSS, entry.VerifyChecksumInFlash(&checksum));
+  EXPECT_EQ(Status::DATA_LOSS, entry.VerifyChecksumInFlash());
 
   // The in-memory verification fills in 0s for the padding.
-  EXPECT_EQ(Status::OK, entry.VerifyChecksum(&checksum, "key45", kValue1));
+  EXPECT_EQ(Status::OK, entry.VerifyChecksum("key45", kValue1));
 
   flash.buffer()[kEntry1.size() - 1] = byte{0};
-  EXPECT_EQ(Status::OK, entry.VerifyChecksumInFlash(&checksum));
+  EXPECT_EQ(Status::OK, entry.VerifyChecksumInFlash());
 }
 }  // namespace
 }  // namespace pw::kvs::internal
diff --git a/pw_kvs/format.cc b/pw_kvs/format.cc
new file mode 100644
index 0000000..e1756a7
--- /dev/null
+++ b/pw_kvs/format.cc
@@ -0,0 +1,28 @@
+// 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 "pw_kvs/format.h"
+
+namespace pw::kvs::internal {
+
+const EntryFormat* EntryFormats::Find(const uint32_t magic) const {
+  for (const EntryFormat& format : formats_) {
+    if (format.magic == magic) {
+      return &format;
+    }
+  }
+  return nullptr;
+}
+
+}  // namespace pw::kvs::internal
diff --git a/pw_kvs/key_value_store.cc b/pw_kvs/key_value_store.cc
index 8e859f2..eb1631f 100644
--- a/pw_kvs/key_value_store.cc
+++ b/pw_kvs/key_value_store.cc
@@ -19,6 +19,8 @@
 #include <cstring>
 #include <type_traits>
 
+#include "pw_kvs/format.h"
+
 #define PW_LOG_USE_ULTRA_SHORT_NAMES 1
 #include "pw_kvs/internal/entry.h"
 #include "pw_kvs_private/macros.h"
@@ -39,10 +41,10 @@
 KeyValueStore::KeyValueStore(FlashPartition* partition,
                              Vector<KeyDescriptor>& key_descriptor_list,
                              Vector<SectorDescriptor>& sector_descriptor_list,
-                             const EntryFormat& format,
+                             span<const EntryFormat> formats,
                              const Options& options)
     : partition_(*partition),
-      entry_header_format_(format),
+      formats_(formats),
       key_descriptors_(key_descriptor_list),
       sectors_(sector_descriptor_list),
       options_(options) {
@@ -169,7 +171,7 @@
   for (KeyDescriptor& key_descriptor : key_descriptors_) {
     for (auto& address : key_descriptor.addresses()) {
       Entry entry;
-      TRY(Entry::Read(partition_, address, &entry));
+      TRY(Entry::Read(partition_, key_descriptor.address(), formats_, &entry));
       SectorFromAddress(address)->AddValidBytes(entry.size());
     }
     if (key_descriptor.IsNewerThan(last_transaction_id_)) {
@@ -242,24 +244,14 @@
 Status KeyValueStore::LoadEntry(Address entry_address,
                                 Address* next_entry_address) {
   Entry entry;
-  TRY(Entry::Read(partition_, entry_address, &entry));
-
-  // TODO: Handle multiple magics for formats that have changed.
-  if (entry.magic() != entry_header_format_.magic) {
-    // TODO: It may be cleaner to have some logging helpers for these cases.
-    ERR("Found corrupt magic: %zx; expecting %zx; at address %zx",
-        size_t(entry.magic()),
-        size_t(entry_header_format_.magic),
-        size_t(entry_address));
-    return Status::DATA_LOSS;
-  }
+  TRY(Entry::Read(partition_, entry_address, formats_, &entry));
 
   // Read the key from flash & validate the entry (which reads the value).
   Entry::KeyBuffer key_buffer;
   TRY_ASSIGN(size_t key_length, entry.ReadKey(key_buffer));
   const string_view key(key_buffer.data(), key_length);
 
-  TRY(entry.VerifyChecksumInFlash(entry_header_format_.checksum));
+  TRY(entry.VerifyChecksumInFlash());
 
   // A valid entry was found, so update the next entry address before doing any
   // of the checks that happen in AppendNewOrOverwriteStaleExistingDescriptor().
@@ -284,10 +276,9 @@
   for (Address address = AlignUp(start_address, Entry::kMinAlignmentBytes);
        AddressInSector(sector, address);
        address += Entry::kMinAlignmentBytes) {
-    // TODO: Handle multiple magics for formats that have changed.
     uint32_t magic;
     TRY(partition_.Read(address, as_writable_bytes(span(&magic, 1))));
-    if (magic == entry_header_format_.magic) {
+    if (formats_.KnownMagic(magic)) {
       DBG("Found entry magic at address %zx", size_t(address));
       *next_entry_address = address;
       return Status::OK;
@@ -419,7 +410,9 @@
   key_buffer_.fill('\0');
 
   Entry entry;
-  if (Entry::Read(kvs_.partition_, descriptor_->address(), &entry).ok()) {
+  if (Entry::Read(
+          kvs_.partition_, descriptor_->address(), kvs_.formats_, &entry)
+          .ok()) {
     entry.ReadKey(key_buffer_);
   }
 }
@@ -469,12 +462,13 @@
                                   span<std::byte> value_buffer,
                                   size_t offset_bytes) const {
   Entry entry;
-  TRY_WITH_SIZE(Entry::Read(partition_, descriptor.address(), &entry));
+  TRY_WITH_SIZE(
+      Entry::Read(partition_, descriptor.address(), formats_, &entry));
 
   StatusWithSize result = entry.ReadValue(value_buffer, offset_bytes);
   if (result.ok() && options_.verify_on_read && offset_bytes == 0u) {
-    Status verify_result = entry.VerifyChecksum(
-        entry_header_format_.checksum, key, value_buffer.first(result.size()));
+    Status verify_result =
+        entry.VerifyChecksum(key, value_buffer.first(result.size()));
     if (!verify_result.ok()) {
       std::memset(value_buffer.data(), 0, result.size());
       return StatusWithSize(verify_result, 0);
@@ -517,7 +511,8 @@
 
 StatusWithSize KeyValueStore::ValueSize(const KeyDescriptor& descriptor) const {
   Entry entry;
-  TRY_WITH_SIZE(Entry::Read(partition_, descriptor.address(), &entry));
+  TRY_WITH_SIZE(
+      Entry::Read(partition_, descriptor.address(), formats_, &entry));
 
   return StatusWithSize(entry.value_size());
 }
@@ -589,7 +584,8 @@
                                                span<const byte> value) {
   // Find the original entry and sector to update the sector's valid_bytes.
   Entry original_entry;
-  TRY(Entry::Read(partition_, key_descriptor->address(), &original_entry));
+  TRY(Entry::Read(
+      partition_, key_descriptor->address(), formats_, &original_entry));
 
   SectorDescriptor* sector;
   TRY(FindOrRecoverSectorWithSpace(&sector,
@@ -650,7 +646,7 @@
   // store the key and value in the TempEntry stored in the static allocated
   // working_buffer_.
   Entry entry;
-  TRY(Entry::Read(partition_, key_descriptor.address(), &entry));
+  TRY(Entry::Read(partition_, key_descriptor.address(), formats_, &entry));
 
   TRY_ASSIGN(size_t key_length, entry.ReadKey(key_buffer));
   string_view key = string_view(key_buffer.data(), key_length);
@@ -661,7 +657,7 @@
   }
 
   const span value = span(value_buffer.data(), result.size());
-  TRY(entry.VerifyChecksum(entry_header_format_.checksum, key, value));
+  TRY(entry.VerifyChecksum(key, value));
 
   // Find a new sector for the entry and write it to the new location. For
   // relocation the find should not not be a sector already containing the key
@@ -927,7 +923,7 @@
   }
 
   if (options_.verify_on_write) {
-    TRY(entry.VerifyChecksumInFlash(entry_header_format_.checksum));
+    TRY(entry.VerifyChecksumInFlash());
   }
 
   // Entry was written successfully; update the key descriptor and the sector
@@ -957,11 +953,11 @@
 
   if (state == KeyDescriptor::kDeleted) {
     return Entry::Tombstone(
-        partition_, address, entry_header_format_, key, last_transaction_id_);
+        partition_, address, formats_.primary(), key, last_transaction_id_);
   }
   return Entry::Valid(partition_,
                       address,
-                      entry_header_format_,
+                      formats_.primary(),
                       key,
                       value,
                       last_transaction_id_);
diff --git a/pw_kvs/key_value_store_binary_format_test.cc b/pw_kvs/key_value_store_binary_format_test.cc
index d429992..19f0354 100644
--- a/pw_kvs/key_value_store_binary_format_test.cc
+++ b/pw_kvs/key_value_store_binary_format_test.cc
@@ -18,6 +18,7 @@
 
 #include "gtest/gtest.h"
 #include "pw_kvs/crc16_checksum.h"
+#include "pw_kvs/format.h"
 #include "pw_kvs/in_memory_fake_flash.h"
 #include "pw_kvs/internal/hash.h"
 #include "pw_kvs/key_value_store.h"
@@ -32,27 +33,31 @@
 constexpr size_t kMaxEntries = 256;
 constexpr size_t kMaxUsableSectors = 256;
 
-constexpr uint32_t SimpleChecksum(span<const byte> data, uint32_t state = 0) {
+constexpr uint32_t SimpleChecksum(span<const byte> data, uint32_t state) {
   for (byte b : data) {
     state += uint32_t(b);
   }
   return state;
 }
 
-class SimpleChecksumAlgorithm final : public ChecksumAlgorithm {
+template <typename State>
+class ChecksumFunction final : public ChecksumAlgorithm {
  public:
-  SimpleChecksumAlgorithm()
-      : ChecksumAlgorithm(as_bytes(span(&checksum_, 1))) {}
+  ChecksumFunction(State (&algorithm)(span<const byte>, State))
+      : ChecksumAlgorithm(as_bytes(span(&state_, 1))), algorithm_(algorithm) {}
 
-  void Reset() override { checksum_ = 0; }
+  void Reset() override { state_ = {}; }
 
   void Update(span<const byte> data) override {
-    checksum_ = SimpleChecksum(data, checksum_);
+    state_ = algorithm_(data, state_);
   }
 
  private:
-  uint32_t checksum_;
-} checksum;
+  State state_;
+  State (&algorithm_)(span<const byte>, State);
+};
+
+ChecksumFunction<uint32_t> checksum(SimpleChecksum);
 
 // Returns a buffer containing the necessary padding for an entry.
 template <size_t kAlignmentBytes, size_t kKeyLength, size_t kValueSize>
@@ -63,7 +68,8 @@
 }
 
 // Creates a buffer containing a valid entry at compile time.
-template <size_t kAlignmentBytes = sizeof(internal::EntryHeader),
+template <uint32_t (*kChecksum)(span<const byte>, uint32_t) = &SimpleChecksum,
+          size_t kAlignmentBytes = sizeof(internal::EntryHeader),
           size_t kKeyLengthWithNull,
           size_t kValueSize>
 constexpr auto MakeValidEntry(uint32_t magic,
@@ -83,7 +89,7 @@
                       EntryPadding<kAlignmentBytes, kKeyLength, kValueSize>());
 
   // Calculate the checksum
-  uint32_t checksum = SimpleChecksum(data);
+  uint32_t checksum = kChecksum(data, 0);
   for (size_t i = 0; i < sizeof(checksum); ++i) {
     data[4 + i] = byte(checksum & 0xff);
     checksum >>= 8;
@@ -93,7 +99,6 @@
 }
 
 constexpr uint32_t kMagic = 0xc001beef;
-constexpr EntryFormat kFormat{.magic = kMagic, .checksum = &checksum};
 constexpr Options kNoGcOptions{
     .gc_on_write = GargbageCollectOnWrite::kDisabled,
     .verify_on_read = true,
@@ -110,7 +115,9 @@
   KvsErrorHandling()
       : flash_(internal::Entry::kMinAlignmentBytes),
         partition_(&flash_),
-        kvs_(&partition_, kFormat, kNoGcOptions) {}
+        kvs_(&partition_,
+             {.magic = kMagic, .checksum = &checksum},
+             kNoGcOptions) {}
 
   void InitFlashTo(span<const byte> contents) {
     partition_.Erase();
@@ -287,5 +294,94 @@
   EXPECT_EQ(stats.writable_bytes, 512u * 3 - 32 * 2);
 }
 
+constexpr uint32_t kAltMagic = 0xbadD00D;
+
+constexpr uint32_t AltChecksum(span<const byte> data, uint32_t state) {
+  for (byte b : data) {
+    state = (state << 8) | uint32_t(byte(state >> 24) ^ b);
+  }
+  return state;
+}
+
+ChecksumFunction<uint32_t> alt_checksum(AltChecksum);
+
+constexpr auto kAltEntry =
+    MakeValidEntry<AltChecksum>(kAltMagic, 32, "A Key", ByteStr("XD"));
+
+constexpr uint32_t NoChecksum(span<const byte>, uint32_t) { return 0; }
+constexpr uint32_t kNoChecksumMagic = 0x6000061e;
+
+constexpr auto kNoChecksumEntry =
+    MakeValidEntry<NoChecksum>(kNoChecksumMagic, 64, "kee", ByteStr("O_o"));
+
+class InitializedMultiMagicKvs : public ::testing::Test {
+ protected:
+  static constexpr auto kInitialContents =
+      AsBytes(kNoChecksumEntry, kEntry1, kAltEntry, kEntry2, kEntry3);
+
+  InitializedMultiMagicKvs()
+      : flash_(internal::Entry::kMinAlignmentBytes),
+        partition_(&flash_),
+        kvs_(&partition_,
+             {{
+                 {.magic = kMagic, .checksum = &checksum},
+                 {.magic = kAltMagic, .checksum = &alt_checksum},
+                 {.magic = kNoChecksumMagic, .checksum = nullptr},
+             }},
+             kNoGcOptions) {
+    partition_.Erase();
+    std::memcpy(flash_.buffer().data(),
+                kInitialContents.data(),
+                kInitialContents.size());
+
+    EXPECT_EQ(Status::OK, kvs_.Init());
+  }
+
+  FakeFlashBuffer<512, 4, 3> flash_;
+  FlashPartition partition_;
+  KeyValueStoreBuffer<kMaxEntries, kMaxUsableSectors, 3> kvs_;
+};
+
+#define ASSERT_CONTAINS_ENTRY(key, str_value)                          \
+  do {                                                                 \
+    char val[sizeof(str_value)] = {};                                  \
+    StatusWithSize stat = kvs_.Get(key, as_writable_bytes(span(val))); \
+    ASSERT_EQ(Status::OK, stat.status());                              \
+    ASSERT_EQ(sizeof(str_value) - 1, stat.size());                     \
+    ASSERT_STREQ(str_value, val);                                      \
+  } while (0)
+
+TEST_F(InitializedMultiMagicKvs, AllEntriesArePresent) {
+  ASSERT_CONTAINS_ENTRY("key1", "value1");
+  ASSERT_CONTAINS_ENTRY("k2", "value2");
+  ASSERT_CONTAINS_ENTRY("k3y", "value3");
+  ASSERT_CONTAINS_ENTRY("A Key", "XD");
+  ASSERT_CONTAINS_ENTRY("kee", "O_o");
+}
+
+TEST_F(InitializedMultiMagicKvs, PutNewEntry_UsesFirstFormat) {
+  EXPECT_EQ(Status::OK, kvs_.Put("new key", ByteStr("abcd?")));
+
+  constexpr auto kNewEntry =
+      MakeValidEntry(kMagic, 65, "new key", ByteStr("abcd?"));
+  EXPECT_EQ(0,
+            std::memcmp(kNewEntry.data(),
+                        flash_.buffer().data() + kInitialContents.size(),
+                        kNewEntry.size()));
+  ASSERT_CONTAINS_ENTRY("new key", "abcd?");
+}
+
+TEST_F(InitializedMultiMagicKvs, PutExistingEntry_UsesFirstFormat) {
+  EXPECT_EQ(Status::OK, kvs_.Put("A Key", ByteStr("New value!")));
+
+  constexpr auto kNewEntry =
+      MakeValidEntry(kMagic, 65, "A Key", ByteStr("New value!"));
+  EXPECT_EQ(0,
+            std::memcmp(kNewEntry.data(),
+                        flash_.buffer().data() + kInitialContents.size(),
+                        kNewEntry.size()));
+  ASSERT_CONTAINS_ENTRY("A Key", "New value!");
+}
+
 }  // namespace
 }  // namespace pw::kvs
diff --git a/pw_kvs/key_value_store_fuzz_test.cc b/pw_kvs/key_value_store_fuzz_test.cc
index ea30bd9..05384bd 100644
--- a/pw_kvs/key_value_store_fuzz_test.cc
+++ b/pw_kvs/key_value_store_fuzz_test.cc
@@ -30,11 +30,11 @@
 FlashPartition test_partition(&test_flash, 0, test_flash.sector_count());
 
 ChecksumCrc16 checksum;
-constexpr EntryFormat kFormat{.magic = 0xBAD'C0D3, .checksum = &checksum};
 
 class EmptyInitializedKvs : public ::testing::Test {
  protected:
-  EmptyInitializedKvs() : kvs_(&test_partition, kFormat) {
+  EmptyInitializedKvs()
+      : kvs_(&test_partition, {.magic = 0xBAD'C0D3, .checksum = &checksum}) {
     test_partition.Erase(0, test_partition.sector_count());
     ASSERT_EQ(Status::OK, kvs_.Init());
   }
diff --git a/pw_kvs/key_value_store_map_test.cc b/pw_kvs/key_value_store_map_test.cc
index 99b76d2..a6b2555 100644
--- a/pw_kvs/key_value_store_map_test.cc
+++ b/pw_kvs/key_value_store_map_test.cc
@@ -78,15 +78,12 @@
 template <const TestParameters& kParams>
 class KvsTester {
  public:
-  static constexpr EntryFormat kFormat{.magic = 0xBAD'C0D3,
-                                       .checksum = nullptr};
-
   KvsTester()
       : partition_(&flash_,
                    kParams.partition_start_sector,
                    kParams.partition_sector_count,
                    kParams.partition_alignment),
-        kvs_(&partition_, kFormat) {
+        kvs_(&partition_, {.magic = 0xBAD'C0D3, .checksum = nullptr}) {
     EXPECT_EQ(Status::OK, partition_.Erase());
     Status result = kvs_.Init();
     EXPECT_EQ(Status::OK, result);
diff --git a/pw_kvs/public/pw_kvs/format.h b/pw_kvs/public/pw_kvs/format.h
index 8a206c9..a2d843a 100644
--- a/pw_kvs/public/pw_kvs/format.h
+++ b/pw_kvs/public/pw_kvs/format.h
@@ -13,7 +13,15 @@
 // the License.
 #pragma once
 
+#include <cstdint>
+
+#include "pw_kvs/checksum.h"
+#include "pw_span/span.h"
+
 namespace pw::kvs {
+
+struct EntryFormat;
+
 namespace internal {
 
 // Disk format of the header used for each key-value entry.
@@ -44,6 +52,26 @@
 
 static_assert(sizeof(EntryHeader) == 16, "EntryHeader must not have padding");
 
+// This class wraps EntryFormat instances to support having multiple
+// simultaneously supported formats.
+class EntryFormats {
+ public:
+  explicit constexpr EntryFormats(span<const EntryFormat> formats)
+      : formats_(formats) {}
+
+  explicit constexpr EntryFormats(const EntryFormat& format)
+      : formats_(&format, 1) {}
+
+  const EntryFormat& primary() const { return formats_.front(); }
+
+  bool KnownMagic(uint32_t magic) const { return Find(magic) != nullptr; }
+
+  const EntryFormat* Find(uint32_t magic) const;
+
+ private:
+  const span<const EntryFormat> formats_;
+};
+
 }  // namespace internal
 
 // The EntryFormat defines properties of KVS entries that use a particular magic
diff --git a/pw_kvs/public/pw_kvs/internal/entry.h b/pw_kvs/public/pw_kvs/internal/entry.h
index 89b98e9..773e4c3 100644
--- a/pw_kvs/public/pw_kvs/internal/entry.h
+++ b/pw_kvs/public/pw_kvs/internal/entry.h
@@ -47,7 +47,10 @@
   //   NOT_FOUND: read the header, but the data appears to be erased
   //   DATA_LOSS: read the header, but it contained invalid data
   //
-  static Status Read(FlashPartition& partition, Address address, Entry* entry);
+  static Status Read(FlashPartition& partition,
+                     Address address,
+                     const internal::EntryFormats& formats,
+                     Entry* entry);
 
   // Reads a key into a buffer, which must be at least key_length bytes.
   static Status ReadKey(FlashPartition& partition,
@@ -112,11 +115,10 @@
   StatusWithSize ReadValue(span<std::byte> buffer,
                            size_t offset_bytes = 0) const;
 
-  Status VerifyChecksum(ChecksumAlgorithm* algorithm,
-                        std::string_view key,
+  Status VerifyChecksum(std::string_view key,
                         span<const std::byte> value) const;
 
-  Status VerifyChecksumInFlash(ChecksumAlgorithm* algorithm) const;
+  Status VerifyChecksumInFlash() const;
 
   // Calculates the total size of an entry, including padding.
   static size_t size(const FlashPartition& partition,
@@ -176,15 +178,18 @@
 
   constexpr Entry(FlashPartition* partition,
                   Address address,
+                  const EntryFormat& format,
                   EntryHeader header)
-      : partition_(partition), address_(address), header_(header) {}
+      : partition_(partition),
+        address_(address),
+        checksum_(format.checksum),
+        header_(header) {}
 
   span<const std::byte> checksum_bytes() const {
     return as_bytes(span(&header_.checksum, 1));
   }
 
-  span<const std::byte> CalculateChecksum(ChecksumAlgorithm* algorithm,
-                                          std::string_view key,
+  span<const std::byte> CalculateChecksum(std::string_view key,
                                           span<const std::byte> value) const;
 
   static constexpr uint8_t alignment_bytes_to_units(size_t alignment_bytes) {
@@ -193,6 +198,7 @@
 
   FlashPartition* partition_;
   Address address_;
+  ChecksumAlgorithm* checksum_;
   EntryHeader header_;
 };
 
diff --git a/pw_kvs/public/pw_kvs/key_value_store.h b/pw_kvs/public/pw_kvs/key_value_store.h
index 5451bc4..8b6cecf 100644
--- a/pw_kvs/public/pw_kvs/key_value_store.h
+++ b/pw_kvs/public/pw_kvs/key_value_store.h
@@ -297,7 +297,7 @@
   KeyValueStore(FlashPartition* partition,
                 Vector<KeyDescriptor>& key_descriptor_list,
                 Vector<SectorDescriptor>& sector_descriptor_list,
-                const EntryFormat& format,
+                span<const EntryFormat> format,
                 const Options& options);
 
  private:
@@ -426,7 +426,7 @@
   void LogKeyDescriptor() const;
 
   FlashPartition& partition_;
-  const EntryFormat entry_header_format_;
+  const internal::EntryFormats formats_;
 
   // Unordered list of KeyDescriptors. Finding a key requires scanning and
   // verifying a match by reading the actual entry.
@@ -457,20 +457,42 @@
   std::array<std::byte, kWorkingBufferSizeBytes> working_buffer_;
 };
 
-template <size_t kMaxEntries, size_t kMaxUsableSectors>
+template <size_t kMaxEntries,
+          size_t kMaxUsableSectors,
+          size_t kEntryFormats = 1>
 class KeyValueStoreBuffer : public KeyValueStore {
  public:
+  // Constructs a KeyValueStore on the partition, with support for one
+  // EntryFormat (kEntryFormats must be 1).
   KeyValueStoreBuffer(FlashPartition* partition,
                       const EntryFormat& format,
                       const Options& options = {})
-      : KeyValueStore(partition, key_descriptors_, sectors_, format, options) {}
+      : KeyValueStoreBuffer(
+            partition,
+            span(reinterpret_cast<const EntryFormat (&)[1]>(format)),
+            options) {
+    static_assert(kEntryFormats == 1,
+                  "kEntryFormats EntryFormats must be specified");
+  }
+
+  // Constructs a KeyValueStore on the partition. Supports multiple entry
+  // formats. The first EntryFormat is used for new entries.
+  KeyValueStoreBuffer(FlashPartition* partition,
+                      span<const EntryFormat, kEntryFormats> formats,
+                      const Options& options = {})
+      : KeyValueStore(
+            partition, key_descriptors_, sectors_, formats_, options) {
+    std::copy(formats.begin(), formats.end(), formats_.begin());
+  }
 
  private:
   static_assert(kMaxEntries > 0u);
   static_assert(kMaxUsableSectors > 0u);
+  static_assert(kEntryFormats > 0u);
 
   Vector<KeyDescriptor, kMaxEntries> key_descriptors_;
   Vector<SectorDescriptor, kMaxUsableSectors> sectors_;
+  std::array<EntryFormat, kEntryFormats> formats_;
 };
 
 }  // namespace pw::kvs