diff --git a/compiler/util-klib/src/org/jetbrains/kotlin/library/SearchPathResolver.kt b/compiler/util-klib/src/org/jetbrains/kotlin/library/SearchPathResolver.kt
index 005b850..6b2024b 100644
--- a/compiler/util-klib/src/org/jetbrains/kotlin/library/SearchPathResolver.kt
+++ b/compiler/util-klib/src/org/jetbrains/kotlin/library/SearchPathResolver.kt
@@ -31,13 +31,28 @@
      */
     class SearchRoot(val searchRootPath: File, val allowLookupByRelativePath: Boolean = false, val isDeprecated: Boolean = false) {
         fun lookUp(libraryPath: File): LookupResult {
-            if (libraryPath.isAbsolute)
+            if (libraryPath.isAbsolute) {
+                // Look up by the absolute path if it is indeed an absolute path.
                 return LookupResult.Found(lookUpByAbsolutePath(libraryPath) ?: return LookupResult.NotFound)
+            }
 
-            if (!allowLookupByRelativePath && libraryPath.nameSegments.size > 1)
+            val isDefinitelyRelativePath = libraryPath.nameSegments.size > 1
+            if (isDefinitelyRelativePath && !allowLookupByRelativePath) {
+                // Lookup by the relative path is disallowed, but the path is definitely a relative path.
                 return LookupResult.NotFound
+            }
 
-            val resolvedLibrary = lookUpByAbsolutePath(File(searchRootPath, libraryPath)) ?: return LookupResult.NotFound
+            // First, try to resolve by the relative path.
+            val resolvedLibrary = lookUpByAbsolutePath(File(searchRootPath, libraryPath))
+                ?: run {
+                    if (!isDefinitelyRelativePath && libraryPath.extension.isEmpty()) {
+                        // If the path actually looks like an unique name of the library, try to guess the name of the KLIB file.
+                        // TODO: This logic is unreliable and needs to be replaced by the new KLIB resolver in the future.
+                        lookUpByAbsolutePath(File(searchRootPath, "${libraryPath.path}.$KLIB_FILE_EXTENSION"))
+                    } else null
+                }
+                ?: return LookupResult.NotFound
+
             return if (isDeprecated)
                 LookupResult.FoundWithWarning(
                     library = resolvedLibrary,
@@ -54,7 +69,7 @@
                 when {
                     absoluteLibraryPath.isFile -> {
                         // It's a really existing file.
-                        when (absoluteLibraryPath.extension.toLowerCase()) {
+                        when (absoluteLibraryPath.extension) {
                             KLIB_FILE_EXTENSION -> absoluteLibraryPath
                             "jar" -> {
                                 // A special workaround for old JS stdlib, that was packed in a JAR file.
diff --git a/compiler/util-klib/src/org/jetbrains/kotlin/library/UnresolvedLibrary.kt b/compiler/util-klib/src/org/jetbrains/kotlin/library/UnresolvedLibrary.kt
index 76afe9f..dcf0653 100644
--- a/compiler/util-klib/src/org/jetbrains/kotlin/library/UnresolvedLibrary.kt
+++ b/compiler/util-klib/src/org/jetbrains/kotlin/library/UnresolvedLibrary.kt
@@ -8,6 +8,15 @@
 fun UnresolvedLibrary(path: String, libraryVersion: String?, lenient: Boolean): UnresolvedLibrary =
     if (lenient) LenientUnresolvedLibrary(path, libraryVersion) else RequiredUnresolvedLibrary(path, libraryVersion)
 
+/**
+ * Representation of a Kotlin library that has not been yet resolved.
+ *
+ * TODO: This class has a major design flaw and needs to be replaced by the new KLIB resolver in the future.
+ * - In certain situations [path] represents a path to the library, would it be relative or absolute.
+ * - In certain situations [path] represents an `unique_name` of the library.
+ * - In general, `unique_name` needs not be equal to the file name of the library. And this adds some mess to the classes
+ *   that implement the "resolver" logic, e.g. [SearchPathResolver].
+ */
 sealed class UnresolvedLibrary {
     abstract val path: String
     abstract val libraryVersion: String?
diff --git a/native/native.tests/tests/org/jetbrains/kotlin/konan/test/blackbox/KlibResolverTest.kt b/native/native.tests/tests/org/jetbrains/kotlin/konan/test/blackbox/KlibResolverTest.kt
new file mode 100644
index 0000000..410352a
--- /dev/null
+++ b/native/native.tests/tests/org/jetbrains/kotlin/konan/test/blackbox/KlibResolverTest.kt
@@ -0,0 +1,156 @@
+/*
+ * Copyright 2010-2023 JetBrains s.r.o. and Kotlin Programming Language contributors.
+ * Use of this source code is governed by the Apache 2.0 license that can be found in the license/LICENSE.txt file.
+ */
+
+package org.jetbrains.kotlin.konan.test.blackbox
+
+import org.jetbrains.kotlin.konan.test.blackbox.support.TestCompilerArgs
+import org.jetbrains.kotlin.konan.test.blackbox.support.compilation.LibraryCompilation
+import org.jetbrains.kotlin.konan.test.blackbox.support.compilation.TestCompilationArtifact.KLIB
+import org.jetbrains.kotlin.konan.test.blackbox.support.compilation.TestCompilationResult.Companion.assertSuccess
+import org.jetbrains.kotlin.library.SearchPathResolver
+import org.junit.jupiter.api.DisplayName
+import org.junit.jupiter.api.Tag
+import org.junit.jupiter.api.Test
+import org.junit.jupiter.api.parallel.Execution
+import org.junit.jupiter.api.parallel.ExecutionMode
+import org.junit.jupiter.api.parallel.Isolated
+import java.io.File
+
+/**
+ * This test class needs to set up a custom working directory in the JVM process. This is necessary to trigger
+ * the special behavior inside the [SearchPathResolver] to start looking for KLIBs by relative path (or just
+ * by library name aka `unique_name`) inside the working directory.
+ *
+ * In order to make this possible and in order to avoid side effects for other tests two special annotations
+ * are added: `@Isolated` and `@Execution(ExecutionMode.SAME_THREAD)`.
+ *
+ * The control over the working directory in performed in the [runWithCustomWorkingDir] function.
+ */
+@Tag("klib")
+@Isolated // Run this test class in isolation from other test classes.
+@Execution(ExecutionMode.SAME_THREAD) // Run all test functions sequentially in the same thread.
+class KlibResolverTest : AbstractNativeSimpleTest() {
+    private data class Module(val name: String, val dependencyNames: List<String>) {
+        constructor(name: String, vararg dependencyNames: String) : this(name, dependencyNames.asList())
+
+        lateinit var dependencies: List<Module>
+        lateinit var sourceFile: File
+
+        fun initDependencies(resolveDependency: (String) -> Module) {
+            dependencies = dependencyNames.map(resolveDependency)
+        }
+    }
+
+    @Test
+    @DisplayName("Test resolving all dependencies recorded in `depends` / `dependency_version` properties (KT-63931)")
+    fun testResolvingDependenciesRecordedInManifest() {
+        val modules = createModules(
+            Module("a"),
+            Module("b", "a"),
+            Module("c", "a"),
+            Module("d", "b", "c", "a"),
+        )
+
+        listOf(
+            false to false,
+            true to false,
+            true to true,
+            false to true,
+        ).forEach { (produceUnpackedKlibs, useLibraryNamesInCliArguments) ->
+            modules.compileModules(produceUnpackedKlibs, useLibraryNamesInCliArguments)
+        }
+    }
+
+    private fun createModules(vararg modules: Module): List<Module> {
+        val mapping: Map<String, Module> = modules.groupBy(Module::name).mapValues {
+            it.value.singleOrNull() ?: error("Duplicated modules: ${it.value}")
+        }
+
+        modules.forEach { it.initDependencies(mapping::getValue) }
+
+        val generatedSourcesDir = buildDir.resolve("generated-sources")
+        generatedSourcesDir.mkdirs()
+
+        modules.forEach { module ->
+            module.sourceFile = generatedSourcesDir.resolve(module.name + ".kt")
+            module.sourceFile.writeText(
+                buildString {
+                    appendLine("package ${module.name}")
+                    appendLine()
+                    appendLine("fun ${module.name}(indent: Int) {")
+                    appendLine("    repeat(indent) { print(\"  \") }")
+                    appendLine("    println(\"${module.name}\")")
+                    module.dependencyNames.forEach { dependencyName ->
+                        appendLine("    $dependencyName.$dependencyName(indent + 1)")
+                    }
+                    appendLine("}")
+                }
+            )
+        }
+
+        return modules.asList()
+    }
+
+    private fun List<Module>.compileModules(
+        produceUnpackedKlibs: Boolean,
+        useLibraryNamesInCliArguments: Boolean
+    ) {
+        val klibFilesDir = buildDir.resolve(
+            listOf(
+                "klib-files",
+                if (produceUnpackedKlibs) "unpacked" else "packed",
+                if (useLibraryNamesInCliArguments) "names" else "paths"
+            ).joinToString(".")
+        )
+        klibFilesDir.mkdirs()
+
+        fun Module.computeArtifactPath(): String {
+            val basePath: String = if (useLibraryNamesInCliArguments) name else klibFilesDir.resolve(name).path
+            return if (produceUnpackedKlibs) basePath else "$basePath.klib"
+        }
+
+        runWithCustomWorkingDir(klibFilesDir) {
+            forEach { module ->
+                val testCase = generateTestCaseWithSingleFile(
+                    sourceFile = module.sourceFile,
+                    moduleName = module.name,
+                    TestCompilerArgs(
+                        buildList {
+                            if (produceUnpackedKlibs) add("-nopack")
+                            module.dependencies.forEach { dependency ->
+                                add("-l")
+                                add(dependency.computeArtifactPath())
+                            }
+                        }
+                    )
+                )
+
+                val compilation = LibraryCompilation(
+                    settings = testRunSettings,
+                    freeCompilerArgs = testCase.freeCompilerArgs,
+                    sourceModules = testCase.modules,
+                    dependencies = emptySet(),
+                    expectedArtifact = KLIB(klibFilesDir.resolve(module.computeArtifactPath()))
+                )
+
+                compilation.result.assertSuccess()
+            }
+        }
+    }
+
+    private inline fun runWithCustomWorkingDir(customWorkingDir: File, block: () -> Unit) {
+        val previousWorkingDir: String = System.getProperty(USER_DIR)
+        try {
+            System.setProperty(USER_DIR, customWorkingDir.absolutePath)
+            block()
+        } finally {
+            System.setProperty(USER_DIR, previousWorkingDir)
+        }
+    }
+
+    companion object {
+        private const val USER_DIR = "user.dir"
+    }
+}