diff --git a/flang/lib/Semantics/check-acc-structure.cpp b/flang/lib/Semantics/check-acc-structure.cpp
--- a/flang/lib/Semantics/check-acc-structure.cpp
+++ b/flang/lib/Semantics/check-acc-structure.cpp
@@ -5,9 +5,10 @@
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
-
 #include "check-acc-structure.h"
+#include "flang/Common/template.h"
 #include "flang/Parser/parse-tree.h"
+#include "flang/Semantics/symbol.h"
 #include "flang/Semantics/tools.h"
 
 #define CHECK_SIMPLE_CLAUSE(X, Y) \
@@ -58,14 +59,41 @@
     currentStatementSourcePosition_ = statement.source;
     return true;
   }
+  bool Pre(const parser::DoConstruct &doConstruct) {
+    const auto &doStmt{
+        std::get<parser::Statement<parser::NonLabelDoStmt>>(doConstruct.t)};
+    if (const auto &name{
+            std::get<std::optional<parser::Name>>(doStmt.statement.t)}) {
+      labels_.insert(*name->symbol);
+    }
+    return true;
+  }
+  SymbolSet labels() { return labels_; }
 
   void Post(const parser::ReturnStmt &) { emitBranchOutError("RETURN"); }
-  void Post(const parser::ExitStmt &) { emitBranchOutError("EXIT"); }
+  void Post(const parser::ExitStmt &exitStmt) {
+    if (const auto &exitName{exitStmt.v}) {
+      checkLabelUse("EXIT", *exitName->symbol);
+    }
+  }
   void Post(const parser::StopStmt &) { emitBranchOutError("STOP"); }
-
 private:
-  parser::MessageFixedText GetEnclosingMsg() {
-    return "Enclosing block construct"_en_US;
+  parser::MessageFormattedText GetEnclosingMsg() {
+    return {"Enclosing %s construct"_en_US,
+        parser::ToUpperCaseLetters(
+            llvm::acc::getOpenACCDirectiveName(currentDirective_).str())};
+  }
+
+  void checkLabelUse(const char *stmt, const Symbol &sym) {
+    if (labels_.find(sym) == labels_.end()) {
+      context_
+          .Say(currentStatementSourcePosition_,
+              "%s to a label '%s' outside of %s construct is not allowed"_err_en_US,
+              stmt, sym.name().ToString(),
+              parser::ToUpperCaseLetters(
+                  llvm::acc::getOpenACCDirectiveName(currentDirective_).str()))
+          .Attach(sourcePosition_, GetEnclosingMsg());
+    }
   }
 
   void emitBranchOutError(const char *stmt) {
@@ -78,6 +106,7 @@
   }
 
   SemanticsContext &context_;
+  SymbolSet labels_;
   parser::CharBlock currentStatementSourcePosition_;
   parser::CharBlock sourcePosition_;
   llvm::acc::Directive currentDirective_;
diff --git a/flang/test/Semantics/acc-branch.f90 b/flang/test/Semantics/acc-branch.f90
--- a/flang/test/Semantics/acc-branch.f90
+++ b/flang/test/Semantics/acc-branch.f90
@@ -7,7 +7,7 @@
 
   implicit none
 
-  integer :: i
+  integer :: i, j, k
   integer :: N = 256
   real(8) :: a(256)
 
@@ -25,12 +25,28 @@
   do i = 1, N
     a(i) = 3.14
     if(i == N-1) THEN
-      !ERROR: EXIT statement is not allowed in a PARALLEL construct
       exit
     end if
   end do
   !$acc end parallel
 
+  label1: do k=1, N
+  !$acc parallel
+  !$acc loop
+  outer: do i=1, N
+    inner: do j=1, N
+      if (j == 2) then
+        exit
+        exit inner
+        exit outer
+        !ERROR: EXIT to a label 'label1' outside of PARALLEL construct is not allowed
+        exit label1
+      end if
+    end do inner
+  end do outer
+  !$acc end parallel
+  end do label1
+
   !$acc parallel
   !$acc loop
   do i = 1, N
@@ -54,7 +70,6 @@
   do i = 1, N
     a(i) = 3.14
     if(i == N-1) THEN
-      !ERROR: EXIT statement is not allowed in a KERNELS construct
       exit
     end if
   end do
@@ -82,12 +97,23 @@
   do i = 1, N
     a(i) = 3.14
     if(i == N-1) THEN
-      !ERROR: EXIT statement is not allowed in a SERIAL construct
       exit
     end if
   end do
   !$acc end serial
 
+  label2: do k=1, N
+  !$acc serial
+  do i = 1, N
+    a(i) = 3.14
+    if(i == N-1) THEN
+        !ERROR: EXIT to a label 'label2' outside of SERIAL construct is not allowed
+        exit label2
+      end if
+    end do
+  !$acc end serial
+  end do label2
+
   !$acc serial
   do i = 1, N
     a(i) = 3.14