diff --git a/libc/src/threads/linux/mtx_unlock.cpp b/libc/src/threads/linux/mtx_unlock.cpp
--- a/libc/src/threads/linux/mtx_unlock.cpp
+++ b/libc/src/threads/linux/mtx_unlock.cpp
@@ -12,6 +12,7 @@
 #include "src/__support/common.h"
 #include "src/threads/linux/thread_utils.h"
 
+#include <limits.h>
 #include <linux/futex.h> // For futex operations.
 #include <stdatomic.h>   // for atomic_compare_exchange_strong.
 
@@ -23,9 +24,14 @@
   while (true) {
     uint32_t mutex_status = MS_Waiting;
     if (atomic_compare_exchange_strong(futex_word, &mutex_status, MS_Free)) {
-      // If any thread is waiting to be woken up, then do it.
-      __llvm_libc::syscall(SYS_futex, futex_word, FUTEX_WAKE_PRIVATE, 1, 0, 0,
-                           0);
+      // If any thread is waiting to be woken up, then do it. We wake up all
+      // waiters as this will ensure that the correct mutex status gets set.
+      // If we wake up only one waiter, then that waiter will lock the mutex
+      // with status MS_Locked and never realize that there are other waiters.
+      // But waking up all waiters, we make sure that the waiters which do not
+      // get the lock set the status back to MS_Waiting.
+      __llvm_libc::syscall(SYS_futex, futex_word, FUTEX_WAKE_PRIVATE, INT_MAX,
+                           0, 0, 0);
       return thrd_success;
     }
 
diff --git a/libc/test/src/threads/mtx_test.cpp b/libc/test/src/threads/mtx_test.cpp
--- a/libc/test/src/threads/mtx_test.cpp
+++ b/libc/test/src/threads/mtx_test.cpp
@@ -127,3 +127,56 @@
   __llvm_libc::thrd_join(&thread, &retval);
   ASSERT_EQ(retval, 0);
 }
+
+static constexpr int THREAD_COUNT = 10;
+static mtx_t multiple_waiter_lock;
+static mtx_t counter_lock;
+static int wait_count = 0;
+
+int waiter_func(void *) {
+  __llvm_libc::mtx_lock(&counter_lock);
+  ++wait_count;
+  __llvm_libc::mtx_unlock(&counter_lock);
+
+  // Block on the waiter lock until the main
+  // thread unblocks.
+  __llvm_libc::mtx_lock(&multiple_waiter_lock);
+  __llvm_libc::mtx_unlock(&multiple_waiter_lock);
+
+  __llvm_libc::mtx_lock(&counter_lock);
+  --wait_count;
+  __llvm_libc::mtx_unlock(&counter_lock);
+
+  return 0;
+}
+
+TEST(MutexTest, MultipleWaiters) {
+  __llvm_libc::mtx_init(&multiple_waiter_lock, mtx_plain);
+  __llvm_libc::mtx_init(&counter_lock, mtx_plain);
+
+  __llvm_libc::mtx_lock(&multiple_waiter_lock);
+  thrd_t waiters[THREAD_COUNT];
+  for (int i = 0; i < THREAD_COUNT; ++i) {
+    __llvm_libc::thrd_create(waiters + i, waiter_func, nullptr);
+  }
+
+  // Spin until the counter is incremented to the desired
+  // value.
+  while (true) {
+    __llvm_libc::mtx_lock(&counter_lock);
+    if (wait_count == THREAD_COUNT) {
+      __llvm_libc::mtx_unlock(&counter_lock);
+      break;
+    }
+    __llvm_libc::mtx_unlock(&counter_lock);
+  }
+
+  __llvm_libc::mtx_unlock(&multiple_waiter_lock);
+
+  int retval;
+  for (int i = 0; i < THREAD_COUNT; ++i) {
+    __llvm_libc::thrd_join(waiters + i, &retval);
+  }
+
+  ASSERT_EQ(wait_count, 0);
+}