diff --git a/mlir/lib/IR/Verifier.cpp b/mlir/lib/IR/Verifier.cpp
--- a/mlir/lib/IR/Verifier.cpp
+++ b/mlir/lib/IR/Verifier.cpp
@@ -52,15 +52,14 @@
   LogicalResult verifyOpAndDominance(Operation &op);
 
 private:
+  /// Any ops that have regions and are marked as "isolated from above" will be
+  /// returned in the opsWithIsolatedRegions vector.
   LogicalResult
   verifyBlock(Block &block,
               SmallVectorImpl<Operation *> &opsWithIsolatedRegions);
-  /// Verify the properties and dominance relationships of this operation,
-  /// stopping region recursion at any "isolated from above operations".  Any
-  /// such ops are returned in the opsWithIsolatedRegions vector.
-  LogicalResult
-  verifyOperation(Operation &op,
-                  SmallVectorImpl<Operation *> &opsWithIsolatedRegions);
+
+  /// Verify the properties and dominance relationships of this operation.
+  LogicalResult verifyOperation(Operation &op);
 
   /// Verify the dominance property of regions contained within the given
   /// Operation.
@@ -74,10 +73,8 @@
 } // namespace
 
 LogicalResult OperationVerifier::verifyOpAndDominance(Operation &op) {
-  SmallVector<Operation *> opsWithIsolatedRegions;
-
   // Verify the operation first, collecting any IsolatedFromAbove operations.
-  if (failed(verifyOperation(op, opsWithIsolatedRegions)))
+  if (failed(verifyOperation(op)))
     return failure();
 
   // Since everything looks structurally ok to this point, we do a dominance
@@ -90,15 +87,7 @@
       return failure();
   }
 
-  // If we aren't verifying nested operations, then we're done.
-  if (!verifyRecursively)
-    return success();
-
-  // Otherwise, check the dominance properties and invariants of any operations
-  // in the regions contained by the 'opsWithIsolatedRegions' operations.
-  return failableParallelForEach(
-      op.getContext(), opsWithIsolatedRegions,
-      [&](Operation *op) { return verifyOpAndDominance(*op); });
+  return success();
 }
 
 /// Returns true if this block may be valid without terminator. That is if:
@@ -150,7 +139,7 @@
       opsWithIsolatedRegions.push_back(&op);
 
       // Otherwise, check the operation inline.
-    } else if (failed(verifyOperation(op, opsWithIsolatedRegions))) {
+    } else if (failed(verifyOperation(op))) {
       return failure();
     }
   }
@@ -177,8 +166,7 @@
 /// Verify the properties and dominance relationships of this operation,
 /// stopping region recursion at any "isolated from above operations".  Any such
 /// ops are returned in the opsWithIsolatedRegions vector.
-LogicalResult OperationVerifier::verifyOperation(
-    Operation &op, SmallVectorImpl<Operation *> &opsWithIsolatedRegions) {
+LogicalResult OperationVerifier::verifyOperation(Operation &op) {
   // Check that operands are non-nil and structurally ok.
   for (auto operand : op.getOperands())
     if (!operand)
@@ -198,6 +186,8 @@
   if (registeredInfo && failed(registeredInfo->verifyInvariants(&op)))
     return failure();
 
+  SmallVector<Operation *> opsWithIsolatedRegions;
+
   if (unsigned numRegions = op.getNumRegions()) {
     auto kindInterface = dyn_cast<RegionKindInterface>(op);
 
@@ -238,6 +228,12 @@
     }
   }
 
+  // Verify the nested ops that are able to be verified in parallel.
+  if (failed(failableParallelForEach(
+          op.getContext(), opsWithIsolatedRegions,
+          [&](Operation *op) { return verifyOpAndDominance(*op); })))
+    return failure();
+
   // After the region ops are verified, run the verifiers that have additional
   // region invariants need to veirfy.
   if (registeredInfo && failed(registeredInfo->verifyRegionInvariants(&op)))
diff --git a/mlir/test/Dialect/Func/invalid.mlir b/mlir/test/Dialect/Func/invalid.mlir
--- a/mlir/test/Dialect/Func/invalid.mlir
+++ b/mlir/test/Dialect/Func/invalid.mlir
@@ -8,7 +8,7 @@
 
 // -----
 
-func @return_i32_f32() -> (i32, f32)
+func private @return_i32_f32() -> (i32, f32)
 
 func @call() {
   // expected-error @+3 {{op result type mismatch at index 0}}
diff --git a/mlir/test/Dialect/MemRef/invalid.mlir b/mlir/test/Dialect/MemRef/invalid.mlir
--- a/mlir/test/Dialect/MemRef/invalid.mlir
+++ b/mlir/test/Dialect/MemRef/invalid.mlir
@@ -351,7 +351,7 @@
 
 // -----
 
-func @foo()
+func private @foo()
 
 func @nonexistent_global_memref() {
   // expected-error @+1 {{'foo' does not reference a valid global memref}}
diff --git a/mlir/test/IR/invalid.mlir b/mlir/test/IR/invalid.mlir
--- a/mlir/test/IR/invalid.mlir
+++ b/mlir/test/IR/invalid.mlir
@@ -565,8 +565,8 @@
 
 // -----
 
-func @redef()  // expected-note {{see existing symbol definition here}}
-func @redef()  // expected-error {{redefinition of symbol named 'redef'}}
+func private @redef()  // expected-note {{see existing symbol definition here}}
+func private @redef()  // expected-error {{redefinition of symbol named 'redef'}}
 
 // -----
 
diff --git a/mlir/test/IR/test-verification-order.mlir b/mlir/test/IR/test-verification-order.mlir
new file mode 100644
--- /dev/null
+++ b/mlir/test/IR/test-verification-order.mlir
@@ -0,0 +1,55 @@
+// RUN: mlir-opt --mlir-disable-threading -split-input-file -verify-diagnostics %s
+
+func @verify_operand_type() {
+  %0 = arith.constant 1 : index
+  // expected-error@+1 {{op operand #0 must be 32-bit signless integer, but got 'index'}}
+  "test.verifiers"(%0) ({
+    %1 = arith.constant 2 : index
+  }) : (index) -> ()
+  return
+}
+
+// -----
+
+func @verify_nested_op_block_trait() {
+  %0 = arith.constant 1 : i32
+  // expected-remark@+1 {{success run of verifier}}
+  "test.verifiers"(%0) ({
+    %1 = arith.constant 2 : index
+    // expected-error@+1 {{op requires one region}}
+    "test.verifiers"(%1) : (index) -> ()
+  }) : (i32) -> ()
+  return
+}
+
+// -----
+
+func @verify_nested_op_operand() {
+  %0 = arith.constant 1 : i32
+  // expected-remark@+1 {{success run of verifier}}
+  "test.verifiers"(%0) ({
+    %1 = arith.constant 2 : index
+    // expected-error@+1 {{op operand #0 must be 32-bit signless integer, but got 'index'}}
+    "test.verifiers"(%1) ({
+      %2 = arith.constant 3 : index
+    }) : (index) -> ()
+  }) : (i32) -> ()
+  return
+}
+
+// -----
+
+func @verify_nested_isolated_above() {
+  %0 = arith.constant 1 : i32
+  // expected-remark@+1 {{success run of verifier}}
+  "test.verifiers"(%0) ({
+    // expected-remark@-1 {{success run of region verifier}}
+    %1 = arith.constant 2 : i32
+    // expected-remark@+1 {{success run of verifier}}
+    "test.verifiers"(%1) ({
+      // expected-remark@-1 {{success run of region verifier}}
+      %2 = arith.constant 3 : index
+    }) : (i32) -> ()
+  }) : (i32) -> ()
+  return
+}
diff --git a/mlir/test/lib/Dialect/Test/TestDialect.cpp b/mlir/test/lib/Dialect/Test/TestDialect.cpp
--- a/mlir/test/lib/Dialect/Test/TestDialect.cpp
+++ b/mlir/test/lib/Dialect/Test/TestDialect.cpp
@@ -18,6 +18,7 @@
 #include "mlir/IR/DialectImplementation.h"
 #include "mlir/IR/PatternMatch.h"
 #include "mlir/IR/TypeUtilities.h"
+#include "mlir/IR/Verifier.h"
 #include "mlir/Reducer/ReductionPatternInterface.h"
 #include "mlir/Transforms/FoldUtils.h"
 #include "mlir/Transforms/InliningUtils.h"
@@ -1305,6 +1306,37 @@
       /*printBlockTerminators=*/false);
 }
 
+//===----------------------------------------------------------------------===//
+// TestVerifiersOp
+//===----------------------------------------------------------------------===//
+
+LogicalResult TestVerifiersOp::verify() {
+  if (!getRegion().hasOneBlock())
+    return emitOpError("`hasOneBlock` trait hasn't been verified");
+
+  Operation *definingOp = getInput().getDefiningOp();
+  if (definingOp && failed(mlir::verify(definingOp)))
+    return emitOpError("operand hasn't been verified");
+
+  emitRemark("success run of verifier");
+
+  return success();
+}
+
+LogicalResult TestVerifiersOp::verifyRegions() {
+  if (!getRegion().hasOneBlock())
+    return emitOpError("`hasOneBlock` trait hasn't been verified");
+
+  for (Block &block : getRegion())
+    for (Operation &op : block)
+      if (failed(mlir::verify(&op)))
+        return emitOpError("nested op hasn't been verified");
+
+  emitRemark("success run of region verifier");
+
+  return success();
+}
+
 #include "TestOpEnums.cpp.inc"
 #include "TestOpInterfaces.cpp.inc"
 #include "TestOpStructs.cpp.inc"
diff --git a/mlir/test/lib/Dialect/Test/TestOps.td b/mlir/test/lib/Dialect/Test/TestOps.td
--- a/mlir/test/lib/Dialect/Test/TestOps.td
+++ b/mlir/test/lib/Dialect/Test/TestOps.td
@@ -2780,4 +2780,16 @@
 def TestEffectsWrite : TEST_Op<"op_with_memwrite",
     [MemoryEffects<[MemWrite]>]>;
 
+//===----------------------------------------------------------------------===//
+// Test Ops with verifiers
+//===----------------------------------------------------------------------===//
+
+def TestVerifiersOp : TEST_Op<"verifiers",
+                              [SingleBlock, NoTerminator, IsolatedFromAbove]> {
+  let arguments = (ins I32:$input);
+  let regions = (region SizedRegion<1>:$region);
+  let hasVerifier = 1;
+  let hasRegionVerifier = 1;
+}
+
 #endif // TEST_OPS