diff --git a/quiche/oblivious_http/common/oblivious_http_header_key_config.cc b/quiche/oblivious_http/common/oblivious_http_header_key_config.cc
index f046ea1..3d3679f 100644
--- a/quiche/oblivious_http/common/oblivious_http_header_key_config.cc
+++ b/quiche/oblivious_http/common/oblivious_http_header_key_config.cc
@@ -291,10 +291,18 @@
 ObliviousHttpKeyConfigs::ParseConcatenatedKeys(absl::string_view key_config) {
   ConfigMap configs;
   PublicKeyMap keys;
-  auto reader = QuicheDataReader(key_config);
+  // First, try to parse the keys using the length-prefixed format from RFC
+  // 9458.
+  if (ReadKeyConfigsWithLengthPrefix(key_config, configs, keys).ok()) {
+    return ObliviousHttpKeyConfigs(std::move(configs), std::move(keys));
+  }
+  // Otherwise, try parsing using the non-length-prefixed format from
+  // draft-ietf-ohai-ohttp-08, a precursor to RFC 9458.
+  configs.clear();
+  keys.clear();
+  QuicheDataReader reader(key_config);
   while (!reader.IsDoneReading()) {
-    absl::Status status = ReadSingleKeyConfig(reader, configs, keys);
-    if (!status.ok()) return status;
+    QUICHE_RETURN_IF_ERROR(ReadSingleKeyConfig(reader, configs, keys));
   }
   return ObliviousHttpKeyConfigs(std::move(configs), std::move(keys));
 }
@@ -364,7 +372,8 @@
 }
 
 absl::Status ObliviousHttpKeyConfigs::ReadSingleKeyConfig(
-    QuicheDataReader& reader, ConfigMap& configs, PublicKeyMap& keys) {
+    QuicheDataReader& reader, ConfigMap& configs, PublicKeyMap& keys,
+    bool skip_unknown_kems) {
   uint8_t key_id;
   if (!reader.ReadUInt8(&key_id)) {
     return absl::InvalidArgumentError("Failed to read key_id");
@@ -373,8 +382,14 @@
   if (!reader.ReadUInt16(&kem_id)) {
     return absl::InvalidArgumentError("Failed to read kem_id");
   }
-  QUICHE_ASSIGN_OR_RETURN(uint16_t key_length, KeyLength(kem_id));
-  std::string key_str(key_length, '\0');
+  absl::StatusOr<uint16_t> key_length = KeyLength(kem_id);
+  if (!key_length.ok()) {
+    if (skip_unknown_kems) {
+      return absl::OkStatus();
+    }
+    return key_length.status();
+  }
+  std::string key_str(*key_length, '\0');
   if (!reader.ReadBytes(key_str.data(), key_str.size())) {
     return absl::InvalidArgumentError("Failed to read public key");
   }
@@ -420,6 +435,26 @@
   return absl::OkStatus();
 }
 
+// static
+absl::Status ObliviousHttpKeyConfigs::ReadKeyConfigsWithLengthPrefix(
+    absl::string_view key_configs, ConfigMap& configs, PublicKeyMap& keys) {
+  QuicheDataReader reader(key_configs);
+  while (!reader.IsDoneReading()) {
+    absl::string_view single_key_config;
+    if (!reader.ReadStringPiece16(&single_key_config)) {
+      return absl::InvalidArgumentError(
+          "Failed to read length-prefixed key config");
+    }
+    QuicheDataReader single_reader(single_key_config);
+    QUICHE_RETURN_IF_ERROR(ReadSingleKeyConfig(single_reader, configs, keys,
+                                               /*skip_unknown_kems=*/true));
+  }
+  if (configs.empty() || keys.empty()) {
+    return absl::InvalidArgumentError("No supported key configs found");
+  }
+  return absl::OkStatus();
+}
+
 // https://www.iana.org/assignments/hpke
 
 std::string ObliviousHttpKemIdToString(uint16_t kem_id) {
diff --git a/quiche/oblivious_http/common/oblivious_http_header_key_config.h b/quiche/oblivious_http/common/oblivious_http_header_key_config.h
index e20e67e..d3954b3 100644
--- a/quiche/oblivious_http/common/oblivious_http_header_key_config.h
+++ b/quiche/oblivious_http/common/oblivious_http_header_key_config.h
@@ -228,7 +228,14 @@
 
   static absl::Status ReadSingleKeyConfig(QuicheDataReader& reader,
                                           ConfigMap& configs,
-                                          PublicKeyMap& keys);
+                                          PublicKeyMap& keys,
+                                          bool skip_unknown_kems = false);
+
+  // Reads key configs from a byte string formatted according to
+  // https://www.rfc-editor.org/rfc/rfc9458.html#section-3.1-2. Note that this
+  // can leave `configs` and `keys` in an invalid state when returning an error.
+  static absl::Status ReadKeyConfigsWithLengthPrefix(
+      absl::string_view key_configs, ConfigMap& configs, PublicKeyMap& keys);
 
   // A mapping from key_id to ObliviousHttpHeaderKeyConfig objects for that key.
   const ConfigMap configs_;
diff --git a/quiche/oblivious_http/common/oblivious_http_header_key_config_test.cc b/quiche/oblivious_http/common/oblivious_http_header_key_config_test.cc
index 1f2cc64..938c4cd 100644
--- a/quiche/oblivious_http/common/oblivious_http_header_key_config_test.cc
+++ b/quiche/oblivious_http/common/oblivious_http_header_key_config_test.cc
@@ -277,6 +277,34 @@
             HasKdfId(EVP_HPKE_HKDF_SHA256), HasAeadId(EVP_HPKE_AES_128_GCM)));
 }
 
+TEST(ObliviousHttpKeyConfigs, TwoSimilarKeyConfigsWithLengthPrefix) {
+  std::string key;
+  ASSERT_TRUE(absl::HexStringToBytes(
+      // First key config.
+      "0029"                              // length of this key config
+      "4b"                                // key_id
+      "0020"                              // kem_id
+      "606162636465666768696a6b6c6d6e6f"  // public_key
+      "707172737475767778797a7b7c7d7e7f"  // public_key
+      "0004"                              // len(symmetric_algorithms)
+      "00010002"                          // HKDF_SHA256, AES_256_GCM
+      // Second key config.
+      "0029"                              // length of this key config
+      "4f"                                // key_id
+      "0020"                              // kem_id
+      "606162636465666768696a6b6c6d6e6f"  // public_key
+      "707172737475767778797a7b7c7d7e7f"  // public_key
+      "0004"                              // len(symmetric_algorithms)
+      "00010001",                         // HKDF_SHA256, AES_128_GCM
+      &key));
+  EXPECT_THAT(ObliviousHttpKeyConfigs::ParseConcatenatedKeys(key),
+              IsOkAndHolds(Property(&ObliviousHttpKeyConfigs::NumKeys, 2)));
+  EXPECT_THAT(
+      ObliviousHttpKeyConfigs::ParseConcatenatedKeys(key)->PreferredConfig(),
+      AllOf(HasKeyId(0x4f), HasKemId(EVP_HPKE_DHKEM_X25519_HKDF_SHA256),
+            HasKdfId(EVP_HPKE_HKDF_SHA256), HasAeadId(EVP_HPKE_AES_128_GCM)));
+}
+
 TEST(ObliviousHttpKeyConfigs, RFCExample) {
   std::string key;
   ASSERT_TRUE(absl::HexStringToBytes(
@@ -300,6 +328,29 @@
   EXPECT_THAT(configs->DebugString(), HasSubstr("31e1f05a7401"));
 }
 
+TEST(ObliviousHttpKeyConfigs, RFCExampleWithLengthPrefix) {
+  std::string key;
+  ASSERT_TRUE(
+      absl::HexStringToBytes("002d01002031e1f05a740102115220e9af918f738674aec95"
+                             "f54db6e04eb705aae8e79815500080001000100010003",
+                             &key));
+  auto configs = ObliviousHttpKeyConfigs::ParseConcatenatedKeys(key);
+  QUICHE_ASSERT_OK(configs);
+  EXPECT_THAT(*configs, Property(&ObliviousHttpKeyConfigs::NumKeys, 1));
+  EXPECT_THAT(
+      configs->PreferredConfig(),
+      AllOf(HasKeyId(0x01), HasKemId(EVP_HPKE_DHKEM_X25519_HKDF_SHA256),
+            HasKdfId(EVP_HPKE_HKDF_SHA256), HasAeadId(EVP_HPKE_AES_128_GCM)));
+  std::string expected_public_key;
+  ASSERT_TRUE(absl::HexStringToBytes(
+      "31e1f05a740102115220e9af918f738674aec95f54db6e04eb705aae8e798155",
+      &expected_public_key));
+  EXPECT_THAT(configs->GetPublicKeyForId(configs->PreferredConfig().GetKeyId()),
+              IsOkAndHolds(expected_public_key));
+  EXPECT_THAT(configs->DebugString(), HasSubstr("AES-128-GCM"));
+  EXPECT_THAT(configs->DebugString(), HasSubstr("31e1f05a7401"));
+}
+
 TEST(ObliviousHttpKeyConfigs, DuplicateKeyId) {
   std::string key;
   ASSERT_TRUE(absl::HexStringToBytes(