diff --git a/tests/store.scm b/tests/store.scm
index 45948f4f43..224b9867c4 100644
--- a/tests/store.scm
+++ b/tests/store.scm
@@ -1,5 +1,5 @@
 ;;; GNU Guix --- Functional package management for GNU
-;;; Copyright © 2012-2021, 2023 Ludovic Courtès <ludo@gnu.org>
+;;; Copyright © 2012-2021, 2023, 2024 Ludovic Courtès <ludo@gnu.org>
 ;;;
 ;;; This file is part of GNU Guix.
 ;;;
@@ -35,6 +35,7 @@ (define-module (test-store)
   #:use-module (gnu packages bootstrap)
   #:use-module (ice-9 match)
   #:use-module (ice-9 regex)
+  #:use-module (ice-9 threads)
   #:use-module (rnrs bytevectors)
   #:use-module (rnrs io ports)
   #:use-module (web uri)
@@ -1042,6 +1043,52 @@ (define %shell
       (ensure-path s item)
       (path-info-nar-size (query-path-info s item)))))
 
+(test-assert "substitute deadlock"
+  (with-store s
+    (let* ((guile (package-derivation s %bootstrap-guile (%current-system)))
+           (c (random-text))                      ;contents of the output
+           (drv1 (build-expression->derivation
+                  s "substitute-me1"
+                  `(begin ,c (exit 1))            ;would actually fail
+                  #:guile-for-build guile))
+           (drv2 (build-expression->derivation
+                  s "substitute-me2"
+                  `(begin ,c (exit 1))            ;would actually fail
+                  #:guile-for-build guile))
+           (drv3 (build-expression->derivation
+                  s "depends-on-substitutable1"
+                  `(call-with-output-file %output
+                     (lambda (p)
+                       (display ,c p)))
+                  #:inputs `(("drv1" ,drv1))
+                  #:guile-for-build guile))
+           (drv4 (build-expression->derivation
+                  s "depends-on-substitutable2"
+                  `(call-with-output-file %output
+                     (lambda (p)
+                       (display ,c p)))
+                  #:inputs `(("drv2" ,drv2))
+                  #:guile-for-build guile)))
+      (with-derivation-substitute drv1 c
+        (with-derivation-substitute drv2 c
+          (system* "ls" "-l" "/tmp/subst")
+          (let* ((builder (lambda (drv)
+                            (call-with-new-thread
+                             (lambda ()
+                               (with-store store
+                                 (set-build-options store
+                                                    #:use-substitutes? #t
+                                                    #:substitute-urls
+                                                    (%test-substitute-urls))
+                                 (build-things store
+                                               (list (derivation-file-name drv))))))))
+                 (thread1 (builder drv3))
+                 (thread2 (builder drv4)))
+            (join-thread thread1)
+            (join-thread thread2)
+            (and (valid-path? s (derivation->output-path drv3))
+                 (valid-path? s (derivation->output-path drv4)))))))))
+
 (test-assert "export/import several paths"
   (let* ((texts (unfold (cut >= <> 10)
                         (lambda _ (random-text))