diff --git a/Doc/library/random.rst b/Doc/library/random.rst
index 9964af4..82e900d 100644
--- a/Doc/library/random.rst
+++ b/Doc/library/random.rst
@@ -230,6 +230,13 @@
    If the sample size is larger than the population size, a :exc:`ValueError`
    is raised.
 
+   .. deprecated:: 3.9
+      In the future, the *population* must be a sequence.  Instances of
+      :class:`set` are no longer supported.  The set must first be converted
+      to a :class:`list` or :class:`tuple`, preferably in a deterministic
+      order so that the sample is reproducible.
+
+
 Real-valued distributions
 -------------------------
 
diff --git a/Lib/random.py b/Lib/random.py
index 3243938..f1df18d 100644
--- a/Lib/random.py
+++ b/Lib/random.py
@@ -367,9 +367,12 @@
         # causing them to eat more entropy than necessary.
 
         if isinstance(population, _Set):
+            _warn('Sampling from a set deprecated\n'
+                  'since Python 3.9 and will be removed in a subsequent version.',
+                  DeprecationWarning, 2)
             population = tuple(population)
         if not isinstance(population, _Sequence):
-            raise TypeError("Population must be a sequence or set.  For dicts, use list(d).")
+            raise TypeError("Population must be a sequence.  For dicts or sets, use sorted(d).")
         randbelow = self._randbelow
         n = len(population)
         if not 0 <= k <= n:
diff --git a/Lib/test/test_random.py b/Lib/test/test_random.py
index 50d4e94..42c68dd 100644
--- a/Lib/test/test_random.py
+++ b/Lib/test/test_random.py
@@ -147,7 +147,6 @@
 
     def test_sample_inputs(self):
         # SF bug #801342 -- population can be any iterable defining __len__()
-        self.gen.sample(set(range(20)), 2)
         self.gen.sample(range(20), 2)
         self.gen.sample(range(20), 2)
         self.gen.sample(str('abcdefghijklmnopqrst'), 2)
@@ -156,6 +155,11 @@
     def test_sample_on_dicts(self):
         self.assertRaises(TypeError, self.gen.sample, dict.fromkeys('abcdef'), 2)
 
+    def test_sample_on_sets(self):
+        with self.assertWarns(DeprecationWarning):
+            population = {10, 20, 30, 40, 50, 60, 70}
+            self.gen.sample(population, k=5)
+
     def test_choices(self):
         choices = self.gen.choices
         data = ['red', 'green', 'blue', 'yellow']
diff --git a/Misc/NEWS.d/next/Library/2020-04-18-19-40-00.bpo-40325.KWSvix.rst b/Misc/NEWS.d/next/Library/2020-04-18-19-40-00.bpo-40325.KWSvix.rst
new file mode 100644
index 0000000..3df5fad
--- /dev/null
+++ b/Misc/NEWS.d/next/Library/2020-04-18-19-40-00.bpo-40325.KWSvix.rst
@@ -0,0 +1 @@
+Deprecated support for set objects in random.sample().