diff --git a/Doc/c-api/set.rst b/Doc/c-api/set.rst
index e677c05..2ed93e9 100644
--- a/Doc/c-api/set.rst
+++ b/Doc/c-api/set.rst
@@ -86,6 +86,11 @@
    set on success or *NULL* on failure.  Raise :exc:`TypeError` if *iterable* is
    not actually iterable.
 
+   .. versionchanged:: 2.6
+      Now guaranteed to return a brand-new :class:`frozenset`.  Formerly,
+      frozensets of zero-length were a singleton.  This got in the way of 
+      building-up new frozensets with :meth:`PySet_Add`.
+
 The following functions and macros are available for instances of :class:`set`
 or :class:`frozenset` or instances of their subtypes.
 
@@ -112,9 +117,6 @@
    the *key* is unhashable. Raise :exc:`PyExc_SystemError` if *anyset* is not a
    :class:`set`, :class:`frozenset`, or an instance of a subtype.
 
-The following functions are available for instances of :class:`set` or its
-subtypes but not for instances of :class:`frozenset` or its subtypes.
-
 
 .. cfunction:: int PySet_Add(PyObject *set, PyObject *key)
 
@@ -124,6 +126,14 @@
    Raise a :exc:`SystemError` if *set* is an not an instance of :class:`set` or its
    subtype.
 
+   .. versionchanged:: 2.6
+      Now works with instances of :class:`frozenset` or its subtypes.
+      Like :cfunc:`PyTuple_SetItem` in that it can be used to fill-in the
+      values of brand new frozensets before they are exposed to other code.
+
+The following functions are available for instances of :class:`set` or its
+subtypes but not for instances of :class:`frozenset` or its subtypes.
+
 
 .. cfunction:: int PySet_Discard(PyObject *set, PyObject *key)
 
diff --git a/Objects/setobject.c b/Objects/setobject.c
index c8db7ce..ee11b9f 100644
--- a/Objects/setobject.c
+++ b/Objects/setobject.c
@@ -2142,17 +2142,7 @@
 PyObject *
 PyFrozenSet_New(PyObject *iterable)
 {
-	PyObject *args, *result;
-
-	if (iterable == NULL)
-		args = PyTuple_New(0);
-	else
-		args = PyTuple_Pack(1, iterable);
-	if (args == NULL)
-		return NULL;
-	result = frozenset_new(&PyFrozenSet_Type, args, NULL);
-	Py_DECREF(args);
-	return result;
+	return make_new_set(&PyFrozenSet_Type, iterable);
 }
 
 Py_ssize_t
@@ -2196,13 +2186,13 @@
 }
 
 int
-PySet_Add(PyObject *set, PyObject *key)
+PySet_Add(PyObject *anyset, PyObject *key)
 {
-	if (!PyType_IsSubtype(Py_TYPE(set), &PySet_Type)) {
+	if (!PyAnySet_Check(anyset)) {
 		PyErr_BadInternalCall();
 		return -1;
 	}
-	return set_add_key((PySetObject *)set, key);
+	return set_add_key((PySetObject *)anyset, key);
 }
 
 int
@@ -2345,7 +2335,6 @@
 	f = PyFrozenSet_New(dup);
 	assert(PySet_Size(f) == 3);
 	assert(PyFrozenSet_CheckExact(f));
-	assertRaises(PySet_Add(f, elem) == -1, PyExc_SystemError);
 	assertRaises(PySet_Discard(f, elem) == -1, PyExc_SystemError);
 	assertRaises(PySet_Pop(f) == NULL, PyExc_SystemError);
 	Py_DECREF(f);