diff --git a/src/class_linker.cc b/src/class_linker.cc
index 98d5fe0..b37a468 100644
--- a/src/class_linker.cc
+++ b/src/class_linker.cc
@@ -1967,7 +1967,7 @@
     return;
   }
 
-  CHECK_EQ(klass->GetStatus(), Class::kStatusResolved) << PrettyClass(klass);
+  CHECK(klass->IsResolved()) << PrettyClass(klass);
   klass->SetStatus(Class::kStatusVerifying);
 
   // Verify super class
@@ -1980,7 +1980,7 @@
     if (!super->IsVerified() && !super->IsErroneous()) {
       Runtime::Current()->GetClassLinker()->VerifyClass(super);
     }
-    if (!super->IsVerified()) {
+    if (!super->IsCompileTimeVerified()) {
       error_msg = "Rejecting class ";
       error_msg += PrettyDescriptor(klass);
       error_msg += " that attempts to sub-class erroneous class ";
@@ -2005,16 +2005,22 @@
   const DexFile& dex_file = FindDexFile(klass->GetDexCache());
   Class::Status oat_file_class_status(Class::kStatusNotReady);
   bool preverified = VerifyClassUsingOatFile(dex_file, klass, oat_file_class_status);
-  bool verified = preverified || verifier::MethodVerifier::VerifyClass(klass, error_msg);
-  if (verified) {
+  verifier::MethodVerifier::FailureKind verifier_failure = verifier::MethodVerifier::kNoFailure;
+  if (!preverified) {
+    verifier_failure = verifier::MethodVerifier::VerifyClass(klass, error_msg);
+  }
+  if (preverified || verifier_failure != verifier::MethodVerifier::kHardFailure) {
     if (!preverified && oat_file_class_status == Class::kStatusError) {
       LOG(FATAL) << "Verification failed hard on class " << PrettyDescriptor(klass)
                  << " at compile time, but succeeded at runtime! The verifier must be broken.";
     }
     DCHECK(!Thread::Current()->IsExceptionPending());
+    CHECK(verifier_failure == verifier::MethodVerifier::kNoFailure ||
+          Runtime::Current()->IsCompiler());
     // Make sure all classes referenced by catch blocks are resolved
     ResolveClassExceptionHandlerTypes(dex_file, klass);
-    klass->SetStatus(Class::kStatusVerified);
+    klass->SetStatus(verifier_failure == verifier::MethodVerifier::kNoFailure ?
+                     Class::kStatusVerified : Class::kStatusRetryVerificationAtRuntime);
     // Sanity check that a verified class has GC maps on all methods
     CheckMethodsHaveGcMaps(klass);
   } else {
@@ -2052,7 +2058,7 @@
   if (oat_file_class_status == Class::kStatusVerified || oat_file_class_status == Class::kStatusInitialized) {
     return true;
   }
-  if (oat_file_class_status == Class::kStatusResolved) {
+  if (oat_file_class_status == Class::kStatusRetryVerificationAtRuntime) {
     // Compile time verification failed with a soft error. Compile time verification can fail
     // because we have incomplete type information. Consider the following:
     // class ... {
diff --git a/src/compiler.cc b/src/compiler.cc
index af06de1..dadfc40 100644
--- a/src/compiler.cc
+++ b/src/compiler.cc
@@ -1155,8 +1155,8 @@
      * will be rejected by the verifier and later skipped during compilation in the compiler.
      */
     std::string error_msg;
-    if (!verifier::MethodVerifier::VerifyClass(context->GetDexFile(), context->GetDexCache(),
-        context->GetClassLoader(), class_def_index, error_msg)) {
+    if (verifier::MethodVerifier::VerifyClass(context->GetDexFile(), context->GetDexCache(),
+        context->GetClassLoader(), class_def_index, error_msg) == verifier::MethodVerifier::kHardFailure) {
       const DexFile::ClassDef& class_def = context->GetDexFile()->GetClassDef(class_def_index);
       LOG(ERROR) << "Verification failed on class "
                  << PrettyDescriptor(context->GetDexFile()->GetClassDescriptor(class_def))
@@ -1172,14 +1172,9 @@
     CHECK(Thread::Current()->IsExceptionPending());
     Thread::Current()->ClearException();
     art::Compiler::ClassReference ref(context->GetDexFile(), class_def_index);
-    if (!verifier::MethodVerifier::IsClassRejected(ref)) {
-      // If the erroneous class wasn't rejected by the verifier, it was a soft error. We want
-      // to try verification again at run-time, so move back into the resolved state.
-      klass->SetStatus(Class::kStatusResolved);
-    }
   }
 
-  CHECK(klass->IsVerified() || klass->IsResolved() || klass->IsErroneous()) << PrettyClass(klass);
+  CHECK(klass->IsCompileTimeVerified() || klass->IsErroneous()) << PrettyClass(klass);
   CHECK(!Thread::Current()->IsExceptionPending()) << PrettyTypeOf(Thread::Current()->GetException());
 }
 
diff --git a/src/object.h b/src/object.h
index 9ad02a8..cc1d28e 100644
--- a/src/object.h
+++ b/src/object.h
@@ -1165,6 +1165,14 @@
   // it kStatusResolved. Java allows circularities of the form where a super
   // class has a field that is of the type of the sub class. We need to be able
   // to fully resolve super classes while resolving types for fields.
+  //
+  // kStatusRetryVerificationAtRuntime: The verifier sets a class to
+  // this state if it encounters a soft failure at compile time. This
+  // often happens when there are unresolved classes in other dex
+  // files, and this status marks a class as needing to be verified
+  // again at runtime.
+  //
+  // TODO: Explain the other states
 
   enum Status {
     kStatusError = -1,
@@ -1172,10 +1180,11 @@
     kStatusIdx = 1,  // loaded, DEX idx in super_class_type_idx_ and interfaces_type_idx_
     kStatusLoaded = 2,  // DEX idx values resolved
     kStatusResolved = 3,  // part of linking
-    kStatusVerifying = 4,  // in the process of being verified
-    kStatusVerified = 5,  // logically part of linking; done pre-init
-    kStatusInitializing = 6,  // class init in progress
-    kStatusInitialized = 7,  // ready to go
+    kStatusRetryVerificationAtRuntime = 4,  // compile time verification failed, retry at runtime
+    kStatusVerifying = 5,  // in the process of being verified
+    kStatusVerified = 6,  // logically part of linking; done pre-init
+    kStatusInitializing = 7,  // class init in progress
+    kStatusInitialized = 8,  // ready to go
   };
 
   Status GetStatus() const {
@@ -1205,6 +1214,11 @@
     return GetStatus() >= kStatusResolved;
   }
 
+  // Returns true if the class was compile-time verified.
+  bool IsCompileTimeVerified() const {
+    return GetStatus() >= kStatusRetryVerificationAtRuntime;
+  }
+
   // Returns true if the class has been verified.
   bool IsVerified() const {
     return GetStatus() >= kStatusVerified;
diff --git a/src/verifier/method_verifier.cc b/src/verifier/method_verifier.cc
index c68d6f3..78bc2e9 100644
--- a/src/verifier/method_verifier.cc
+++ b/src/verifier/method_verifier.cc
@@ -172,23 +172,23 @@
   }
 }
 
-bool MethodVerifier::VerifyClass(const Class* klass, std::string& error) {
+MethodVerifier::FailureKind MethodVerifier::VerifyClass(const Class* klass, std::string& error) {
   if (klass->IsVerified()) {
-    return true;
+    return kNoFailure;
   }
   Class* super = klass->GetSuperClass();
   if (super == NULL && StringPiece(ClassHelper(klass).GetDescriptor()) != "Ljava/lang/Object;") {
     error = "Verifier rejected class ";
     error += PrettyDescriptor(klass);
     error += " that has no super class";
-    return false;
+    return kHardFailure;
   }
   if (super != NULL && super->IsFinal()) {
     error = "Verifier rejected class ";
     error += PrettyDescriptor(klass);
     error += " that attempts to sub-class final class ";
     error += PrettyDescriptor(super);
-    return false;
+    return kHardFailure;
   }
   ClassHelper kh(klass);
   const DexFile& dex_file = kh.GetDexFile();
@@ -198,24 +198,25 @@
     error += PrettyDescriptor(klass);
     error += " that isn't present in dex file ";
     error += dex_file.GetLocation();
-    return false;
+    return kHardFailure;
   }
   return VerifyClass(&dex_file, kh.GetDexCache(), klass->GetClassLoader(), class_def_idx, error);
 }
 
-bool MethodVerifier::VerifyClass(const DexFile* dex_file, DexCache* dex_cache,
+MethodVerifier::FailureKind MethodVerifier::VerifyClass(const DexFile* dex_file, DexCache* dex_cache,
     const ClassLoader* class_loader, uint32_t class_def_idx, std::string& error) {
   const DexFile::ClassDef& class_def = dex_file->GetClassDef(class_def_idx);
   const byte* class_data = dex_file->GetClassData(class_def);
   if (class_data == NULL) {
     // empty class, probably a marker interface
-    return true;
+    return kNoFailure;
   }
   ClassDataItemIterator it(*dex_file, class_data);
   while (it.HasNextStaticField() || it.HasNextInstanceField()) {
     it.Next();
   }
   size_t error_count = 0;
+  bool hard_fail = false;
   ClassLinker* linker = Runtime::Current()->GetClassLinker();
   while (it.HasNextDirectMethod()) {
     uint32_t method_idx = it.GetMemberIndex();
@@ -225,15 +226,19 @@
       // We couldn't resolve the method, but continue regardless.
       Thread::Current()->ClearException();
     }
-    if (!VerifyMethod(method_idx, dex_file, dex_cache, class_loader, class_def_idx,
-        it.GetMethodCodeItem(), method, it.GetMemberAccessFlags())) {
-      if (error_count > 0) {
-        error += "\n";
+    MethodVerifier::FailureKind result = VerifyMethod(method_idx, dex_file, dex_cache, class_loader,
+        class_def_idx, it.GetMethodCodeItem(), method, it.GetMemberAccessFlags());
+    if (result != kNoFailure) {
+      if (result == kHardFailure) {
+        hard_fail = true;
+        if (error_count > 0) {
+          error += "\n";
+        }
+        error = "Verifier rejected class ";
+        error += PrettyDescriptor(dex_file->GetClassDescriptor(class_def));
+        error += " due to bad method ";
+        error += PrettyMethod(method_idx, *dex_file);
       }
-      error = "Verifier rejected class ";
-      error += PrettyDescriptor(dex_file->GetClassDescriptor(class_def));
-      error += " due to bad method ";
-      error += PrettyMethod(method_idx, *dex_file);
       ++error_count;
     }
     it.Next();
@@ -246,35 +251,43 @@
       // We couldn't resolve the method, but continue regardless.
       Thread::Current()->ClearException();
     }
-    if (!VerifyMethod(method_idx, dex_file, dex_cache, class_loader, class_def_idx,
-        it.GetMethodCodeItem(), method, it.GetMemberAccessFlags())) {
-      if (error_count > 0) {
-        error += "\n";
+    MethodVerifier::FailureKind result = VerifyMethod(method_idx, dex_file, dex_cache, class_loader,
+        class_def_idx, it.GetMethodCodeItem(), method, it.GetMemberAccessFlags());
+    if (result != kNoFailure) {
+      if (result == kHardFailure) {
+        hard_fail = true;
+        if (error_count > 0) {
+          error += "\n";
+        }
+        error = "Verifier rejected class ";
+        error += PrettyDescriptor(dex_file->GetClassDescriptor(class_def));
+        error += " due to bad method ";
+        error += PrettyMethod(method_idx, *dex_file);
       }
-      error = "Verifier rejected class ";
-      error += PrettyDescriptor(dex_file->GetClassDescriptor(class_def));
-      error += " due to bad method ";
-      error += PrettyMethod(method_idx, *dex_file);
       ++error_count;
     }
     it.Next();
   }
-  return error_count == 0;
+  if (error_count == 0) {
+    return kNoFailure;
+  } else {
+    return hard_fail ? kHardFailure : kSoftFailure;
+  }
 }
 
-bool MethodVerifier::VerifyMethod(uint32_t method_idx, const DexFile* dex_file, DexCache* dex_cache,
-    const ClassLoader* class_loader, uint32_t class_def_idx, const DexFile::CodeItem* code_item,
-    Method* method, uint32_t method_access_flags) {
+MethodVerifier::FailureKind MethodVerifier::VerifyMethod(uint32_t method_idx, const DexFile* dex_file,
+    DexCache* dex_cache, const ClassLoader* class_loader, uint32_t class_def_idx,
+    const DexFile::CodeItem* code_item, Method* method, uint32_t method_access_flags) {
   MethodVerifier verifier(dex_file, dex_cache, class_loader, class_def_idx, code_item, method_idx,
                           method, method_access_flags);
-  bool success = verifier.Verify();
-  if (success) {
+  if (verifier.Verify()) {
     // Verification completed, however failures may be pending that didn't cause the verification
     // to hard fail.
     CHECK(!verifier.have_pending_hard_failure_);
     if (verifier.failures_.size() != 0) {
       verifier.DumpFailures(LOG(INFO) << "Soft verification failures in "
                                       << PrettyMethod(method_idx, *dex_file) << "\n");
+      return kSoftFailure;
     }
   } else {
     // Bad method data.
@@ -286,8 +299,9 @@
       std::cout << "\n" << verifier.info_messages_.str();
       verifier.Dump(std::cout);
     }
+    return kHardFailure;
   }
-  return success;
+  return kNoFailure;
 }
 
 void MethodVerifier::VerifyMethodAndDump(Method* method) {
diff --git a/src/verifier/method_verifier.h b/src/verifier/method_verifier.h
index 639d736..2e4b33f 100644
--- a/src/verifier/method_verifier.h
+++ b/src/verifier/method_verifier.h
@@ -161,9 +161,15 @@
   typedef greenland::InferredRegCategoryMap InferredRegCategoryMap;
 #endif
  public:
-  /* Verify a class. Returns "true" on success. */
-  static bool VerifyClass(const Class* klass, std::string& error);
-  static bool VerifyClass(const DexFile* dex_file, DexCache* dex_cache,
+  enum FailureKind {
+    kNoFailure,
+    kSoftFailure,
+    kHardFailure,
+  };
+
+  /* Verify a class. Returns "kNoFailure" on success. */
+  static FailureKind VerifyClass(const Class* klass, std::string& error);
+  static FailureKind VerifyClass(const DexFile* dex_file, DexCache* dex_cache,
       const ClassLoader* class_loader, uint32_t class_def_idx, std::string& error);
 
   uint8_t EncodePcToReferenceMapData() const;
@@ -227,7 +233,7 @@
    *  (3) Iterate through the method, checking type safety and looking
    *      for code flow problems.
    */
-  static bool VerifyMethod(uint32_t method_idx, const DexFile* dex_file, DexCache* dex_cache,
+  static FailureKind VerifyMethod(uint32_t method_idx, const DexFile* dex_file, DexCache* dex_cache,
       const ClassLoader* class_loader, uint32_t class_def_idx, const DexFile::CodeItem* code_item,
       Method* method, uint32_t method_access_flags);
   static void VerifyMethodAndDump(Method* method);
diff --git a/src/verifier/method_verifier_test.cc b/src/verifier/method_verifier_test.cc
index f35d8a1..5c23e9f 100644
--- a/src/verifier/method_verifier_test.cc
+++ b/src/verifier/method_verifier_test.cc
@@ -33,7 +33,7 @@
 
     // Verify the class
     std::string error_msg;
-    ASSERT_TRUE(MethodVerifier::VerifyClass(klass, error_msg)) << error_msg;
+    ASSERT_TRUE(MethodVerifier::VerifyClass(klass, error_msg) == MethodVerifier::kNoFailure) << error_msg;
   }
 
   void VerifyDexFile(const DexFile* dex) {
@@ -56,7 +56,7 @@
   SirtRef<ClassLoader> class_loader(LoadDex("IntMath"));
   Class* klass = class_linker_->FindClass("LIntMath;", class_loader.get());
   std::string error_msg;
-  ASSERT_TRUE(MethodVerifier::VerifyClass(klass, error_msg)) << error_msg;
+  ASSERT_TRUE(MethodVerifier::VerifyClass(klass, error_msg) == MethodVerifier::kNoFailure) << error_msg;
 }
 
 }  // namespace verifier