diff --git a/Lib/test/test_capi/test_set.py b/Lib/test/test_capi/test_set.py
index 62d90a3..a41c2fc 100644
--- a/Lib/test/test_capi/test_set.py
+++ b/Lib/test/test_capi/test_set.py
@@ -166,6 +166,12 @@ def test_add(self):
         # CRASHES: add(instance, NULL)
         # CRASHES: add(NULL, NULL)
 
+    def test_add_frozenset(self):
+       add = _testlimitedcapi.set_add
+       frozen_set = frozenset()
+       # test adding an element to a non-uniquely referenced frozenset throws an exception
+       self.assertRaises(SystemError, add, frozen_set, 1)
+
     def test_discard(self):
         discard = _testlimitedcapi.set_discard
         for cls in (set, set_subclass):
diff --git a/Lib/test/test_sys.py b/Lib/test/test_sys.py
index a5708b2..b44e0c9 100644
--- a/Lib/test/test_sys.py
+++ b/Lib/test/test_sys.py
@@ -1880,7 +1880,10 @@ class S(set):
         check(S(), set(), '3P')
         class FS(frozenset):
             __slots__ = 'a', 'b', 'c'
-        check(FS(), frozenset(), '3P')
+
+        class mytuple(tuple):
+            pass
+        check(FS([mytuple()]), frozenset([mytuple()]), '3P')
         from collections import OrderedDict
         class OD(OrderedDict):
             __slots__ = 'a', 'b', 'c'
diff --git a/Misc/NEWS.d/next/Core_and_Builtins/2025-10-16-22-36-05.gh-issue-140232.u3srgv.rst b/Misc/NEWS.d/next/Core_and_Builtins/2025-10-16-22-36-05.gh-issue-140232.u3srgv.rst
new file mode 100644
index 0000000..e40daac
--- /dev/null
+++ b/Misc/NEWS.d/next/Core_and_Builtins/2025-10-16-22-36-05.gh-issue-140232.u3srgv.rst
@@ -0,0 +1 @@
+Frozenset objects with immutable elements are no longer tracked by the garbage collector.
diff --git a/Modules/_testlimitedcapi/set.c b/Modules/_testlimitedcapi/set.c
index 34ed6b1..8aade95 100644
--- a/Modules/_testlimitedcapi/set.c
+++ b/Modules/_testlimitedcapi/set.c
@@ -156,6 +156,72 @@ test_frozenset_add_in_capi(PyObject *self, PyObject *Py_UNUSED(obj))
 }
 
 static PyObject *
+raiseTestError(const char* test_name, const char* msg)
+{
+    PyErr_Format(PyExc_AssertionError, "%s: %s", test_name, msg);
+    return NULL;
+}
+
+static PyObject *
+test_frozenset_add_in_capi_tracking_immutable(PyObject *self, PyObject *Py_UNUSED(ignored))
+{
+    // Test: GC tracking - frozenset with only immutable items should not be tracked
+    PyObject *frozenset = PyFrozenSet_New(NULL);
+    if (frozenset == NULL) {
+        return NULL;
+    }
+    if (PySet_Add(frozenset, Py_True) < 0) {
+        Py_DECREF(frozenset);
+        return NULL;
+    }
+    if (PyObject_GC_IsTracked(frozenset)) {
+        Py_DECREF(frozenset);
+        return raiseTestError("test_frozenset_add_in_capi_tracking_immutable",
+                              "frozenset with only bool should not be GC tracked");
+    }
+    Py_DECREF(frozenset);
+    Py_RETURN_NONE;
+}
+
+static PyObject *
+test_frozenset_add_in_capi_tracking(PyObject *self, PyObject *Py_UNUSED(ignored))
+{
+    // Test: GC tracking - frozenset with tracked object should be tracked
+    PyObject *frozenset = PyFrozenSet_New(NULL);
+    if (frozenset == NULL) {
+        return NULL;
+    }
+
+    PyObject *tracked_obj = PyErr_NewException("_testlimitedcapi.py_set_add", NULL, NULL);
+    if (tracked_obj == NULL) {
+        goto error;
+    }
+    if (!PyObject_GC_IsTracked(tracked_obj)) {
+        Py_DECREF(frozenset);
+        Py_DECREF(tracked_obj);
+        return raiseTestError("test_frozenset_add_in_capi_tracking",
+                              "test object should be tracked");
+    }
+    if (PySet_Add(frozenset, tracked_obj) < 0) {
+        goto error;
+    }
+    Py_DECREF(tracked_obj);
+    if (!PyObject_GC_IsTracked(frozenset)) {
+        Py_DECREF(frozenset);
+        return raiseTestError("test_frozenset_add_in_capi_tracking",
+                              "frozenset with with GC tracked object should be tracked");
+    }
+    Py_DECREF(frozenset);
+    Py_RETURN_NONE;
+
+error:
+    Py_DECREF(frozenset);
+    Py_XDECREF(tracked_obj);
+    return NULL;
+}
+
+
+static PyObject *
 test_set_contains_does_not_convert_unhashable_key(PyObject *self, PyObject *Py_UNUSED(obj))
 {
     // See https://docs.python.org/3/c-api/set.html#c.PySet_Contains
@@ -219,6 +285,8 @@ static PyMethodDef test_methods[] = {
     {"set_clear", set_clear, METH_O},
 
     {"test_frozenset_add_in_capi", test_frozenset_add_in_capi, METH_NOARGS},
+    {"test_frozenset_add_in_capi_tracking", test_frozenset_add_in_capi_tracking, METH_NOARGS},
+    {"test_frozenset_add_in_capi_tracking_immutable", test_frozenset_add_in_capi_tracking_immutable, METH_NOARGS},
     {"test_set_contains_does_not_convert_unhashable_key",
      test_set_contains_does_not_convert_unhashable_key, METH_NOARGS},
 
diff --git a/Objects/setobject.c b/Objects/setobject.c
index 378f221..5d4d181 100644
--- a/Objects/setobject.c
+++ b/Objects/setobject.c
@@ -1368,6 +1368,26 @@ make_new_set_basetype(PyTypeObject *type, PyObject *iterable)
     return make_new_set(type, iterable);
 }
 
+// gh-140232: check whether a frozenset can be untracked from the GC
+static void
+_PyFrozenSet_MaybeUntrack(PyObject *op)
+{
+    assert(op != NULL);
+    // subclasses of a frozenset can generate reference cycles, so do not untrack
+    if (!PyFrozenSet_CheckExact(op)) {
+        return;
+    }
+    // if no elements of a frozenset are tracked by the GC, we untrack the object
+    Py_ssize_t pos = 0;
+    setentry *entry;
+    while (set_next((PySetObject *)op, &pos, &entry)) {
+        if (_PyObject_GC_MAY_BE_TRACKED(entry->key)) {
+            return;
+        }
+    }
+    _PyObject_GC_UNTRACK(op);
+}
+
 static PyObject *
 make_new_frozenset(PyTypeObject *type, PyObject *iterable)
 {
@@ -1379,7 +1399,11 @@ make_new_frozenset(PyTypeObject *type, PyObject *iterable)
         /* frozenset(f) is idempotent */
         return Py_NewRef(iterable);
     }
-    return make_new_set(type, iterable);
+    PyObject *obj = make_new_set(type, iterable);
+    if (obj != NULL) {
+        _PyFrozenSet_MaybeUntrack(obj);
+    }
+    return obj;
 }
 
 static PyObject *
@@ -2932,7 +2956,11 @@ PySet_New(PyObject *iterable)
 PyObject *
 PyFrozenSet_New(PyObject *iterable)
 {
-    return make_new_set(&PyFrozenSet_Type, iterable);
+    PyObject *result = make_new_set(&PyFrozenSet_Type, iterable);
+    if (result != NULL) {
+        _PyFrozenSet_MaybeUntrack(result);
+    }
+    return result;
 }
 
 Py_ssize_t
@@ -3010,6 +3038,11 @@ PySet_Add(PyObject *anyset, PyObject *key)
         // API limits the usage of `PySet_Add` to "fill in the values of brand
         // new frozensets before they are exposed to other code". In this case,
         // this can be done without a lock.
+        // Since another key is added to the set, we must track the frozenset
+        // if needed.
+        if (PyFrozenSet_CheckExact(anyset) && !PyObject_GC_IsTracked(anyset) && PyObject_GC_IsTracked(key)) {
+            _PyObject_GC_TRACK(anyset);
+        }
         return set_add_key((PySetObject *)anyset, key);
     }