diff --git a/clang-tools-extra/clangd/Headers.cpp b/clang-tools-extra/clangd/Headers.cpp
--- a/clang-tools-extra/clangd/Headers.cpp
+++ b/clang-tools-extra/clangd/Headers.cpp
@@ -9,6 +9,7 @@
 #include "Headers.h"
 #include "Preamble.h"
 #include "SourceCode.h"
+#include "support/Logger.h"
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Frontend/CompilerInstance.h"
@@ -106,10 +107,19 @@
         InBuiltinFile = false;
       // At file exit time HeaderSearchInfo is valid and can be used to
       // determine whether the file was a self-contained header or not.
-      if (const FileEntry *FE = SM.getFileEntryForID(PrevFID))
+      if (const FileEntry *FE = SM.getFileEntryForID(PrevFID)) {
+        // If a self-contained header is included recursively it will get
+        // different FileIDs each time. Only the last result of
+        // isSelfContainedHeader is reliable, so we should remove the header
+        // from a set of non self-contanied ones if at some point we realze it
+        // wasn't one.
         if (!isSelfContainedHeader(FE, PrevFID, SM, HeaderInfo))
           Out->NonSelfContained.insert(
               *Out->getID(SM.getFileEntryForID(PrevFID)));
+        else
+          Out->NonSelfContained.erase(
+              *Out->getID(SM.getFileEntryForID(PrevFID)));
+      }
       break;
     }
     case PPCallbacks::RenameFile:
diff --git a/clang-tools-extra/clangd/unittests/HeadersTests.cpp b/clang-tools-extra/clangd/unittests/HeadersTests.cpp
--- a/clang-tools-extra/clangd/unittests/HeadersTests.cpp
+++ b/clang-tools-extra/clangd/unittests/HeadersTests.cpp
@@ -383,6 +383,7 @@
 #include "nonguarded.h"
 #include "pp_depend.h"
 #include "pragmaguarded.h"
+#include "recursive.h"
 )cpp";
   FS.Files["pragmaguarded.h"] = R"cpp(
 #pragma once
@@ -400,10 +401,19 @@
   # error You have to have PP directive set to include this one!
   #endif
 )cpp";
+  FS.Files["recursive.h"] = R"cpp(
+  #ifndef RECURSIVE_H
+  #define RECURSIVE_H
+
+  #include "recursive.h"
+  
+  #endif // RECURSIVE_H
+)cpp";
 
   auto Includes = collectIncludes();
   EXPECT_TRUE(Includes.isSelfContained(getID("pragmaguarded.h", Includes)));
   EXPECT_TRUE(Includes.isSelfContained(getID("includeguarded.h", Includes)));
+  EXPECT_TRUE(Includes.isSelfContained(getID("recursive.h", Includes)));
   EXPECT_FALSE(Includes.isSelfContained(getID("nonguarded.h", Includes)));
   EXPECT_FALSE(Includes.isSelfContained(getID("pp_depend.h", Includes)));
 }
diff --git a/clang-tools-extra/clangd/unittests/IncludeCleanerTests.cpp b/clang-tools-extra/clangd/unittests/IncludeCleanerTests.cpp
--- a/clang-tools-extra/clangd/unittests/IncludeCleanerTests.cpp
+++ b/clang-tools-extra/clangd/unittests/IncludeCleanerTests.cpp
@@ -538,6 +538,38 @@
   EXPECT_THAT(Unused, IsEmpty());
 }
 
+TEST(IncludeCleaner, RecursiveInclusion) {
+  TestTU TU;
+  TU.Code = R"cpp(
+    #include "foo.h"
+
+    void baz() {
+      foo();
+    }
+    )cpp";
+  TU.AdditionalFiles["foo.h"] = R"cpp(
+    #ifndef FOO_H
+    #define FOO_H
+
+    void foo() {}
+
+    #include "bar.h"
+
+    #endif
+  )cpp";
+  TU.AdditionalFiles["bar.h"] = guard(R"cpp(
+    #include "foo.h"
+  )cpp");
+  ParsedAST AST = TU.build();
+
+  auto ReferencedFiles = findReferencedFiles(
+      findReferencedLocations(AST), AST.getIncludeStructure(),
+      AST.getCanonicalIncludes(), AST.getSourceManager());
+  EXPECT_THAT(AST.getDiagnostics(), llvm::ValueIs(IsEmpty()));
+  auto Unused = computeUnusedIncludes(AST);
+  EXPECT_THAT(Unused, IsEmpty());
+}
+
 } // namespace
 } // namespace clangd
 } // namespace clang