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']