diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/file/GcDeleteEmptyRefsFoldersTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/file/GcDeleteEmptyRefsFoldersTest.java
index 76e1534..b37cd7a 100644
--- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/file/GcDeleteEmptyRefsFoldersTest.java
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/file/GcDeleteEmptyRefsFoldersTest.java
@@ -46,6 +46,7 @@
 import static org.junit.Assert.assertFalse;
 import static org.junit.Assert.assertTrue;
 
+import java.io.IOException;
 import java.nio.file.Files;
 import java.nio.file.Path;
 import java.nio.file.Paths;
@@ -56,8 +57,8 @@
 import org.junit.Test;
 
 public class GcDeleteEmptyRefsFoldersTest extends GcTestCase {
-	private static final String REF_FOLDER_01 = "01";
-	private static final String REF_FOLDER_02 = "02";
+	private static final String REF_FOLDER_01 = "A/B/01";
+	private static final String REF_FOLDER_02 = "C/D/02";
 
 	private Path refsDir;
 	private Path heads;
@@ -74,23 +75,36 @@
 	@Test
 	public void emptyRefFoldersAreDeleted() throws Exception {
 		FileTime fileTime = FileTime.from(Instant.now().minusSeconds(31));
-		Path refDir01 = Files.createDirectory(heads.resolve(REF_FOLDER_01));
-		Path refDir02 = Files.createDirectory(heads.resolve(REF_FOLDER_02));
-		Files.setLastModifiedTime(refDir01, fileTime);
-		Files.setLastModifiedTime(refDir02, fileTime);
+		Path refDir01 = Files.createDirectories(heads.resolve(REF_FOLDER_01));
+		Path refDir02 = Files.createDirectories(heads.resolve(REF_FOLDER_02));
+		setLastModifiedTime(fileTime, heads, REF_FOLDER_01);
+		setLastModifiedTime(fileTime, heads, REF_FOLDER_02);
 		assertTrue(refDir01.toFile().exists());
 		assertTrue(refDir02.toFile().exists());
 		gc.gc();
 
 		assertFalse(refDir01.toFile().exists());
+		assertFalse(refDir01.getParent().toFile().exists());
+		assertFalse(refDir01.getParent().getParent().toFile().exists());
 		assertFalse(refDir02.toFile().exists());
+		assertFalse(refDir02.getParent().toFile().exists());
+		assertFalse(refDir02.getParent().getParent().toFile().exists());
+	}
+
+	private void setLastModifiedTime(FileTime fileTime, Path path, String folder) throws IOException {
+		long numParents = folder.chars().filter(c -> c == '/').count();
+		Path folderPath = path.resolve(folder);
+		for(int folderLevel = 0; folderLevel <= numParents; folderLevel ++ ) {
+			Files.setLastModifiedTime(folderPath, fileTime);
+			folderPath = folderPath.getParent();
+		}
 	}
 
 	@Test
 	public void emptyRefFoldersAreKeptIfTheyAreTooRecent()
 			throws Exception {
-		Path refDir01 = Files.createDirectory(heads.resolve(REF_FOLDER_01));
-		Path refDir02 = Files.createDirectory(heads.resolve(REF_FOLDER_02));
+		Path refDir01 = Files.createDirectories(heads.resolve(REF_FOLDER_01));
+		Path refDir02 = Files.createDirectories(heads.resolve(REF_FOLDER_02));
 		assertTrue(refDir01.toFile().exists());
 		assertTrue(refDir02.toFile().exists());
 		gc.gc();
@@ -101,8 +115,8 @@
 
 	@Test
 	public void nonEmptyRefsFoldersAreKept() throws Exception {
-		Path refDir01 = Files.createDirectory(heads.resolve(REF_FOLDER_01));
-		Path refDir02 = Files.createDirectory(heads.resolve(REF_FOLDER_02));
+		Path refDir01 = Files.createDirectories(heads.resolve(REF_FOLDER_01));
+		Path refDir02 = Files.createDirectories(heads.resolve(REF_FOLDER_02));
 		Path ref01 = Files.createFile(refDir01.resolve("ref01"));
 		Path ref02 = Files.createFile(refDir01.resolve("ref02"));
 		assertTrue(refDir01.toFile().exists());
diff --git a/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties b/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties
index 68bb68e..16f184b 100644
--- a/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties
+++ b/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties
@@ -45,6 +45,7 @@
 buildingBitmaps=Building bitmaps
 cachedPacksPreventsIndexCreation=Using cached packs prevents index creation
 cachedPacksPreventsListingObjects=Using cached packs prevents listing objects
+cannotAccessLastModifiedForSafeDeletion=Unable to access lastModifiedTime of file {0}, skip deletion since we cannot safely avoid race condition
 cannotBeCombined=Cannot be combined.
 cannotBeRecursiveWhenTreesAreIncluded=TreeWalk shouldn't be recursive when tree objects are included.
 cannotChangeActionOnComment=Cannot change action on comment line in git-rebase-todo file, old action: {0}, new action: {1}.
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java
index 56a2448..4b7459c 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java
@@ -104,6 +104,7 @@
 	/***/ public String buildingBitmaps;
 	/***/ public String cachedPacksPreventsIndexCreation;
 	/***/ public String cachedPacksPreventsListingObjects;
+	/***/ public String cannotAccessLastModifiedForSafeDeletion;
 	/***/ public String cannotBeCombined;
 	/***/ public String cannotBeRecursiveWhenTreesAreIncluded;
 	/***/ public String cannotChangeActionOnComment;
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/GC.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/GC.java
index eb5c1db..d99a485 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/GC.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/GC.java
@@ -885,16 +885,31 @@
 
 	private void deleteEmptyRefsFolders() throws IOException {
 		Path refs = repo.getDirectory().toPath().resolve(Constants.R_REFS);
+		// Avoid deleting a folder that was created after the threshold so that concurrent
+		// operations trying to create a reference are not impacted
+		Instant threshold = Instant.now().minus(30, ChronoUnit.SECONDS);
 		try (Stream<Path> entries = Files.list(refs)) {
 			Iterator<Path> iterator = entries.iterator();
 			while (iterator.hasNext()) {
 				try (Stream<Path> s = Files.list(iterator.next())) {
-					s.forEach(this::deleteDir);
+					s.filter(path -> canBeSafelyDeleted(path, threshold)).forEach(this::deleteDir);
 				}
 			}
 		}
 	}
 
+	private boolean canBeSafelyDeleted(Path path, Instant threshold) {
+		try {
+			return Files.getLastModifiedTime(path).toInstant().isBefore(threshold);
+		}
+		catch (IOException e) {
+			LOG.warn(MessageFormat.format(
+					JGitText.get().cannotAccessLastModifiedForSafeDeletion,
+					path), e);
+			return false;
+		}
+	}
+
 	private void deleteDir(Path dir) {
 		try (Stream<Path> dirs = Files.walk(dir)) {
 			dirs.filter(this::isDirectory).sorted(Comparator.reverseOrder())
@@ -910,16 +925,7 @@
 
 	private void delete(Path d) {
 		try {
-			// Avoid deleting a folder that was just created so that concurrent
-			// operations trying to create a reference are not impacted
-			Instant threshold = Instant.now().minus(30, ChronoUnit.SECONDS);
-			Instant lastModified = Files.getLastModifiedTime(d).toInstant();
-			if (lastModified.isBefore(threshold)) {
-				// If the folder is not empty, the delete operation will fail
-				// silently. This is a cheaper alternative to filtering the
-				// stream in the calling method.
-				Files.delete(d);
-			}
+			Files.delete(d);
 		} catch (IOException e) {
 			LOG.error(MessageFormat.format(JGitText.get().cannotDeleteFile, d),
 					e);