diff --git a/dex2oat/dex2oat.cc b/dex2oat/dex2oat.cc
index 741bc64..3fe9c47 100644
--- a/dex2oat/dex2oat.cc
+++ b/dex2oat/dex2oat.cc
@@ -1249,20 +1249,19 @@
               class_loader_context_arg.c_str());
       }
       if (args.Exists(M::StoredClassLoaderContext)) {
-        stored_class_loader_context_.reset(new std::string(*args.Get(M::StoredClassLoaderContext)));
-        std::unique_ptr<ClassLoaderContext> temp_context =
-            ClassLoaderContext::Create(*stored_class_loader_context_);
-        if (temp_context == nullptr) {
+        const std::string stored_context_arg = *args.Get(M::StoredClassLoaderContext);
+        stored_class_loader_context_ = ClassLoaderContext::Create(stored_context_arg);
+        if (stored_class_loader_context_ == nullptr) {
           Usage("Option --stored-class-loader-context has an incorrect format: %s",
-                stored_class_loader_context_->c_str());
+                stored_context_arg.c_str());
         } else if (!class_loader_context_->VerifyClassLoaderContextMatch(
-            *stored_class_loader_context_,
+            stored_context_arg,
             /*verify_names*/ false,
             /*verify_checksums*/ false)) {
           Usage(
               "Option --stored-class-loader-context '%s' mismatches --class-loader-context '%s'",
-               stored_class_loader_context_->c_str(),
-               class_loader_context_arg.c_str());
+              stored_context_arg.c_str(),
+              class_loader_context_arg.c_str());
         }
       }
     } else if (args.Exists(M::StoredClassLoaderContext)) {
@@ -1609,12 +1608,9 @@
       // Store the class loader context in the oat header.
       // TODO: deprecate this since store_class_loader_context should be enough to cover the users
       // of classpath_dir as well.
-      std::string class_path_key;
-      if (stored_class_loader_context_ != nullptr) {
-        class_path_key = *stored_class_loader_context_;
-      } else {
-        class_path_key = class_loader_context_->EncodeContextForOatFile(classpath_dir_);
-      }
+      std::string class_path_key =
+          class_loader_context_->EncodeContextForOatFile(classpath_dir_,
+                                                         stored_class_loader_context_.get());
       key_value_store_->Put(OatHeader::kClassPathKey, class_path_key);
     }
 
@@ -2822,7 +2818,7 @@
   std::unique_ptr<ClassLoaderContext> class_loader_context_;
 
   // The class loader context stored in the oat file. May be equal to class_loader_context_.
-  std::unique_ptr<std::string> stored_class_loader_context_;
+  std::unique_ptr<ClassLoaderContext> stored_class_loader_context_;
 
   size_t thread_count_;
   uint64_t start_ns_;
diff --git a/dex2oat/dex2oat_test.cc b/dex2oat/dex2oat_test.cc
index 710a6af..bc8468e 100644
--- a/dex2oat/dex2oat_test.cc
+++ b/dex2oat/dex2oat_test.cc
@@ -2126,10 +2126,26 @@
 }
 
 TEST_F(Dex2oatClassLoaderContextTest, StoredClassLoaderContext) {
+  std::vector<std::unique_ptr<const DexFile>> dex_files = OpenTestDexFiles("MultiDex");
   const std::string out_dir = GetScratchDir();
   const std::string odex_location = out_dir + "/base.odex";
-  const std::string valid_context = "PCL[" + GetUsedDexLocation() + "]";
+  const std::string valid_context = "PCL[" + dex_files[0]->GetLocation() + "]";
   const std::string stored_context = "PCL[/system/not_real_lib.jar]";
+  std::string expected_stored_context = "PCL[";
+  size_t index = 1;
+  for (const std::unique_ptr<const DexFile>& dex_file : dex_files) {
+    const bool is_first = index == 1u;
+    if (!is_first) {
+      expected_stored_context += ":";
+    }
+    expected_stored_context += "/system/not_real_lib.jar";
+    if (!is_first) {
+      expected_stored_context += "!classes" + std::to_string(index) + ".dex";
+    }
+    expected_stored_context += "*" + std::to_string(dex_file->GetLocationChecksum());
+    ++index;
+  }
+  expected_stored_context +=    + "]";
   // The class path should not be valid and should fail being stored.
   GenerateOdexForTest(GetTestDexFileName("ManyMethods"),
                       odex_location,
@@ -2138,8 +2154,8 @@
                       true,  // expect_success
                       false,  // use_fd
                       [&](const OatFile& oat_file) {
-    EXPECT_NE(oat_file.GetClassLoaderContext(), stored_context);
-    EXPECT_NE(oat_file.GetClassLoaderContext(), valid_context);
+    EXPECT_NE(oat_file.GetClassLoaderContext(), stored_context) << output_;
+    EXPECT_NE(oat_file.GetClassLoaderContext(), valid_context) << output_;
   });
   // The stored context should match what we expect even though it's invalid.
   GenerateOdexForTest(GetTestDexFileName("ManyMethods"),
@@ -2150,7 +2166,7 @@
                       true,  // expect_success
                       false,  // use_fd
                       [&](const OatFile& oat_file) {
-    EXPECT_EQ(oat_file.GetClassLoaderContext(), stored_context);
+    EXPECT_EQ(oat_file.GetClassLoaderContext(), expected_stored_context) << output_;
   });
 }
 
diff --git a/runtime/class_loader_context.cc b/runtime/class_loader_context.cc
index 216ad8f..4afc44c 100644
--- a/runtime/class_loader_context.cc
+++ b/runtime/class_loader_context.cc
@@ -254,6 +254,7 @@
     // This will allow the context to VerifyClassLoaderContextMatch which expects or multidex
     // location in the class paths.
     // Note that this will also remove the paths that could not be opened.
+    info.original_classpath = std::move(info.classpath);
     info.classpath.clear();
     info.checksums.clear();
     for (size_t k = opened_dex_files_index; k < info.opened_dex_files.size(); k++) {
@@ -294,20 +295,26 @@
 }
 
 std::string ClassLoaderContext::EncodeContextForDex2oat(const std::string& base_dir) const {
-  return EncodeContext(base_dir, /*for_dex2oat*/ true);
+  return EncodeContext(base_dir, /*for_dex2oat*/ true, /*stored_context*/ nullptr);
 }
 
-std::string ClassLoaderContext::EncodeContextForOatFile(const std::string& base_dir) const {
-  return EncodeContext(base_dir, /*for_dex2oat*/ false);
+std::string ClassLoaderContext::EncodeContextForOatFile(const std::string& base_dir,
+                                                        ClassLoaderContext* stored_context) const {
+  return EncodeContext(base_dir, /*for_dex2oat*/ false, stored_context);
 }
 
 std::string ClassLoaderContext::EncodeContext(const std::string& base_dir,
-                                              bool for_dex2oat) const {
+                                              bool for_dex2oat,
+                                              ClassLoaderContext* stored_context) const {
   CheckDexFilesOpened("EncodeContextForOatFile");
   if (special_shared_library_) {
     return OatFile::kSpecialSharedLibrary;
   }
 
+  if (stored_context != nullptr) {
+    DCHECK_EQ(class_loader_chain_.size(), stored_context->class_loader_chain_.size());
+  }
+
   std::ostringstream out;
   if (class_loader_chain_.empty()) {
     // We can get in this situation if the context was created with a class path containing the
@@ -326,6 +333,15 @@
     out << GetClassLoaderTypeName(info.type);
     out << kClassLoaderOpeningMark;
     std::set<std::string> seen_locations;
+    SafeMap<std::string, std::string> remap;
+    if (stored_context != nullptr) {
+      DCHECK_EQ(info.original_classpath.size(),
+                stored_context->class_loader_chain_[i].classpath.size());
+      for (size_t k = 0; k < info.original_classpath.size(); ++k) {
+        // Note that we don't care if the same name appears twice.
+        remap.Put(info.original_classpath[k], stored_context->class_loader_chain_[i].classpath[k]);
+      }
+    }
     for (size_t k = 0; k < info.opened_dex_files.size(); k++) {
       const std::unique_ptr<const DexFile>& dex_file = info.opened_dex_files[k];
       if (for_dex2oat) {
@@ -337,7 +353,14 @@
           continue;
         }
       }
-      const std::string& location = dex_file->GetLocation();
+      std::string location = dex_file->GetLocation();
+      // If there is a stored class loader remap, fix up the multidex strings.
+      if (!remap.empty()) {
+        std::string base_dex_location = DexFileLoader::GetBaseLocation(location);
+        auto it = remap.find(base_dex_location);
+        CHECK(it != remap.end()) << base_dex_location;
+        location = it->second + DexFileLoader::GetMultiDexSuffix(location);
+      }
       if (k > 0) {
         out << kClasspathSeparator;
       }
@@ -345,7 +368,7 @@
       if (!base_dir.empty() && location.substr(0, base_dir.length()) == base_dir) {
         out << location.substr(base_dir.length() + 1).c_str();
       } else {
-        out << dex_file->GetLocation().c_str();
+        out << location.c_str();
       }
       // dex2oat does not need the checksums.
       if (!for_dex2oat) {
@@ -776,4 +799,3 @@
 }
 
 }  // namespace art
-
diff --git a/runtime/class_loader_context.h b/runtime/class_loader_context.h
index 231acc4..1c83007 100644
--- a/runtime/class_loader_context.h
+++ b/runtime/class_loader_context.h
@@ -84,9 +84,12 @@
   // (so that it can be read and verified at runtime against the actual class
   // loader hierarchy).
   // Should only be called if OpenDexFiles() returned true.
+  // If stored context is non-null, the stored names are overwritten by the class path from the
+  // stored context.
   // E.g. if the context is PCL[a.dex:b.dex] this will return
   // "PCL[a.dex*a_checksum*b.dex*a_checksum]".
-  std::string EncodeContextForOatFile(const std::string& base_dir) const;
+  std::string EncodeContextForOatFile(const std::string& base_dir,
+                                      ClassLoaderContext* stored_context = nullptr) const;
 
   // Encodes the context as a string suitable to be passed to dex2oat.
   // This is the same as EncodeContextForOatFile but without adding the checksums
@@ -150,6 +153,8 @@
     // The list of class path elements that this loader loads.
     // Note that this list may contain relative paths.
     std::vector<std::string> classpath;
+    // Original opened class path (ignoring multidex).
+    std::vector<std::string> original_classpath;
     // The list of class path elements checksums.
     // May be empty if the checksums are not given when the context is created.
     std::vector<uint32_t> checksums;
@@ -202,7 +207,9 @@
   // location). Otherwise, for oat files, the encoding adds all the dex files (including multidex)
   // together with their checksums.
   // Should only be called if OpenDexFiles() returned true.
-  std::string EncodeContext(const std::string& base_dir, bool for_dex2oat) const;
+  std::string EncodeContext(const std::string& base_dir,
+                            bool for_dex2oat,
+                            ClassLoaderContext* stored_context) const;
 
   // Extracts the class loader type from the given spec.
   // Return ClassLoaderContext::kInvalidClassLoader if the class loader type is not