diff --git a/src/Core/Banshee.Services/Banshee.Collection.Database/DatabaseTrackListModel.cs b/src/Core/Banshee.Services/Banshee.Collection.Database/DatabaseTrackListModel.cs
index e5e2757..281571b 100644
--- a/src/Core/Banshee.Services/Banshee.Collection.Database/DatabaseTrackListModel.cs
+++ b/src/Core/Banshee.Services/Banshee.Collection.Database/DatabaseTrackListModel.cs
@@ -349,6 +349,11 @@ namespace Banshee.Collection.Database
             AND (LastSkippedStamp < ? OR LastSkippedStamp IS NULL)
             AND (CoreTracks.Rating = ? OR (? = 3 AND CoreTracks.Rating = 0))
             ORDER BY RANDOM()";
+        private static string random_by_score_fragment = @"
+            AND (LastPlayedStamp < ? OR LastPlayedStamp IS NULL)
+            AND (LastSkippedStamp < ? OR LastSkippedStamp IS NULL)
+            AND (CoreTracks.Score BETWEEN ? AND ? OR (? = 50 AND CoreTracks.Score = 0))
+            ORDER BY RANDOM()";
 
         private DateTime random_began_at = DateTime.MinValue;
         private DateTime last_random = DateTime.MinValue;
@@ -424,6 +429,18 @@ namespace Banshee.Collection.Database
                     return cache.GetSingle (random_by_rating_fragment, random_began_at, random_began_at, random_rating, random_rating);
                 }
                 return null;
+            } else if (mode == PlaybackShuffleMode.Score) {
+                int min, max;
+                bool got_score = GetRandomScore (random_began_at, out min, out max);
+                if (!got_score && repeat) {
+                    random_began_at = last_random;
+                    got_score = GetRandomScore (random_began_at, out min, out max);
+                }
+
+                if (got_score) {
+                    return cache.GetSingle (random_by_score_fragment, random_began_at, random_began_at, min, max, max);
+                }
+                return null;
             } else {
                 random_album_id = random_artist_id = null;
             }
@@ -489,16 +506,39 @@ namespace Banshee.Collection.Database
             return artist_id;
         }
 
-        private readonly Random random = new Random ();
         private int GetRandomRating (DateTime stamp)
         {
-            // Default rating for unrated songs.
-            const int unrated_rating = 3;
-            // counts[x] = number of tracks rated x + 1.
-            int[] counts = new int[5];
-            // Get the distribution of ratings for tracks that haven't been played since stamp.
-            using (var reader = connection.Query (@"
-                SELECT t.Rating, COUNT(*)
+            // Number of rating slots.
+            const int slots = 5;
+
+            // Command to retrieve the distribution of ratings for tracks that haven't been played since stamp.
+            var cmd = new HyenaSqliteCommand (@"
+                SELECT (t.Rating - 1) AS Slot, COUNT(*)
+                FROM CoreTracks AS t
+                JOIN CoreCache AS c ON c.ItemID = t.TrackID
+                WHERE
+                    c.ModelID = ? AND
+                    t.LastStreamError = 0 AND
+                    (t.LastPlayedStamp < ? OR t.LastPlayedStamp IS NULL) AND
+                    (t.LastSkippedStamp < ? OR t.LastSkippedStamp IS NULL)
+                GROUP BY Slot",
+                CacheId, stamp, stamp
+            );
+
+            int slot = GetRandomSlot (cmd, slots);
+
+            return slot < 0 ? 0 : slot + 1;
+        }
+
+        private bool GetRandomScore (DateTime stamp, out int min, out int max)
+        {
+            // Number of score slots.
+            const int slots = 20;
+
+            // Command to retrieve the distribution of scores for tracks that haven't been played since stamp.
+            // NOTE: SQLite wrongly assumes that (-1)/5 == 0, the CASE WHEN works around this.
+            var cmd = new HyenaSqliteCommand (@"
+                SELECT CASE WHEN IFNULL(t.Score, 0) = 0 THEN -1 ELSE (t.Score - 1) * ? / 100 END AS Slot, COUNT(*)
                 FROM CoreTracks AS t
                 JOIN CoreCache AS c ON c.ItemID = t.TrackID
                 WHERE
@@ -506,31 +546,53 @@ namespace Banshee.Collection.Database
                     t.LastStreamError = 0 AND
                     (t.LastPlayedStamp < ? OR t.LastPlayedStamp IS NULL) AND
                     (t.LastSkippedStamp < ? OR t.LastSkippedStamp IS NULL)
-                GROUP BY t.Rating",
-                CacheId, stamp, stamp)) {
+                GROUP BY Slot",
+                slots, CacheId, stamp, stamp
+            );
+
+            int slot = GetRandomSlot (cmd, slots);
 
+            if (slot < 0) {
+                min = max = 0;
+                return false;
+            }
+
+            min = slot * 100 / slots + 1;
+            max = (slot + 1) * 100 / slots;
+            return true;
+        }
+
+        private readonly Random random = new Random ();
+        private int GetRandomSlot (HyenaSqliteCommand cmd, int slots)
+        {
+            // counts[x] = number of tracks in slot x.
+            int[] counts = new int[slots];
+            int default_slot = (slots - 1) / 2;
+
+            // Get the distribution for tracks that haven't been played since stamp.
+            using (var reader = connection.Query (cmd)) {
                 while (reader.Read ()) {
-                    int rating = Convert.ToInt32 (reader[0]);
+                    int slot = Convert.ToInt32 (reader[0]);
                     int count = Convert.ToInt32 (reader[1]);
 
-                    if (rating < 1 || rating > 5) {
-                        rating = unrated_rating;
+                    if (slot < 0 || slot >= slots) {
+                        slot = default_slot;
                     }
 
-                    counts[rating - 1] += count;
+                    counts[slot] += count;
                 }
             }
 
             if (counts.Sum () == 0) {
-                return 0;
+                return -1;
             }
 
-            // We will use powers of phi as weights. Such weights result in songs rated R
-            // played as often as songs rated R-1 and R-2 combined.
+            // We will use powers of phi as weights. Such weights result in songs rated R played as often as songs
+            // rated R-1 and R-2 combined. The exponent is adjusted to the number of slots when it's different from 5.
             const double phi = 1.618033989;
 
             // If you change the weights make sure ALL of them are strictly positive.
-            var weights = Enumerable.Range (0, 5).Select (i => Math.Pow (phi, i)).ToArray ();
+            var weights = Enumerable.Range (0, slots).Select (i => Math.Pow (phi, i * 5 / (double) slots)).ToArray ();
 
             // Apply weights to the counts.
             var weighted_counts = counts.Select ((c, i) => c * weights[i]);
@@ -539,17 +601,17 @@ namespace Banshee.Collection.Database
             var weighted_total = weighted_counts.Sum ();
             weighted_counts = weighted_counts.Select (c => c / weighted_total);
 
-            // Now that we have our counts, get a weighted random rating.
+            // Now that we have our counts, get the slot a weighted random track belongs to.
             double random_value = random.NextDouble ();
-            int current_rating = 0;
+            int current_slot = -1;
             foreach (var weighted_count in weighted_counts) {
-                current_rating++;
+                current_slot++;
                 random_value -= weighted_count;
                 if (random_value <= 0.0) {
                     break;
                 }
             }
-            return current_rating;
+            return current_slot;
         }
 
 #endregion
diff --git a/src/Core/Banshee.Services/Banshee.PlaybackController/PlaybackShuffleMode.cs b/src/Core/Banshee.Services/Banshee.PlaybackController/PlaybackShuffleMode.cs
index 1cd3493..8903ce4 100644
--- a/src/Core/Banshee.Services/Banshee.PlaybackController/PlaybackShuffleMode.cs
+++ b/src/Core/Banshee.Services/Banshee.PlaybackController/PlaybackShuffleMode.cs
@@ -36,7 +36,8 @@ namespace Banshee.PlaybackController
         Song,
         Artist,
         Album,
-        Rating
+        Rating,
+        Score
     }
 
     public class ShuffleModeChangedEventArgs : EventArgs
diff --git a/src/Core/Banshee.ThickClient/Banshee.Gui/PlaybackShuffleActions.cs b/src/Core/Banshee.ThickClient/Banshee.Gui/PlaybackShuffleActions.cs
index 1702682..4dc07b7 100644
--- a/src/Core/Banshee.ThickClient/Banshee.Gui/PlaybackShuffleActions.cs
+++ b/src/Core/Banshee.ThickClient/Banshee.Gui/PlaybackShuffleActions.cs
@@ -101,6 +101,11 @@ namespace Banshee.Gui
                     Catalog.GetString ("Shuffle by _Rating"), null,
                     Catalog.GetString ("Play songs randomly, prefer higher rated songs"),
                     (int)PlaybackShuffleMode.Rating),
+
+                new RadioActionEntry ("ShuffleScoreAction", null,
+                    Catalog.GetString ("Shuffle by S_core"), null,
+                    Catalog.GetString ("Play songs randomly, prefer higher scored songs"),
+                    (int)PlaybackShuffleMode.Score)
             }, 0, OnActionChanged);
                 
             this["ShuffleOffAction"].IconName = "media-skip-forward";
@@ -108,6 +113,7 @@ namespace Banshee.Gui
             this["ShuffleArtistAction"].IconName = "media-playlist-shuffle";
             this["ShuffleAlbumAction"].IconName = "media-playlist-shuffle";
             this["ShuffleRatingAction"].IconName = "media-playlist-shuffle";
+            this["ShuffleScoreAction"].IconName = "media-playlist-shuffle";
 
             ServiceManager.PlaybackController.ShuffleModeChanged += OnShuffleModeChanged;
             ServiceManager.PlaybackController.SourceChanged += OnPlaybackSourceChanged;
@@ -205,6 +211,7 @@ namespace Banshee.Gui
             yield return (RadioAction)this["ShuffleArtistAction"];
             yield return (RadioAction)this["ShuffleAlbumAction"];
             yield return (RadioAction)this["ShuffleRatingAction"];
+            yield return (RadioAction)this["ShuffleScoreAction"];
         }
 
         IEnumerator IEnumerable.GetEnumerator ()
@@ -227,7 +234,7 @@ namespace Banshee.Gui
             "playback", "shuffle_mode",
             "off",
             "Shuffle playback",
-            "Shuffle mode (shuffle_off, shuffle_song, shuffle_artist, shuffle_album, shuffle_rating)"
+            "Shuffle mode (shuffle_off, shuffle_song, shuffle_artist, shuffle_album, shuffle_rating, shuffle_score)"
         );
     }
 }
