diff --git a/lisp/net/tramp-sh.el b/lisp/net/tramp-sh.el
index 2d253506dd..86e82d4092 100644
--- a/lisp/net/tramp-sh.el
+++ b/lisp/net/tramp-sh.el
@@ -2547,7 +2547,11 @@ tramp-sh-handle-make-directory
   "Like `make-directory' for Tramp files."
   (setq dir (expand-file-name dir))
   (with-parsed-tramp-file-name dir nil
-    (tramp-flush-directory-properties v (file-name-directory localname))
+    ;; When PARENTS is non-nil, DIR could be a chain of non-existent
+    ;; directories a/b/c/...  Instead of checking, we simply flush the
+    ;; whole cache.
+    (tramp-flush-directory-properties
+     v (if parents "/" (file-name-directory localname)))
     (save-excursion
       (tramp-barf-unless-okay
        v (format "%s %s"