--- a/dom/media/mediasource/TrackBuffersManager.cpp
+++ b/dom/media/mediasource/TrackBuffersManager.cpp
@@ -1920,16 +1920,17 @@ TrackBuffersManager::SkipToNextRandomAcc
       }
       trackData.mNextGetSampleIndex = Some(uint32_t(pos));
     }
   }
 
   TimeUnit nextSampleTimecode = trackData.mNextSampleTimecode;
   TimeUnit nextSampleTime = trackData.mNextSampleTime;
   uint32_t i = trackData.mNextGetSampleIndex.ref();
+  int32_t originalPos = i;
 
   for (; i < track.Length(); i++) {
     const MediaRawData* sample =
       GetSample(aTrack,
                 i,
                 nextSampleTimecode,
                 nextSampleTime,
                 aFuzz);
@@ -1945,20 +1946,39 @@ TrackBuffersManager::SkipToNextRandomAcc
       TimeUnit::FromMicroseconds(sample->mTimecode + sample->mDuration);
     nextSampleTime = TimeUnit::FromMicroseconds(sample->GetEndTime());
     parsed++;
   }
 
   // Adjust the next demux time and index so that the next call to
   // SkipToNextRandomAccessPoint will not count again the parsed sample as
   // skipped.
-  trackData.mNextSampleTimecode = nextSampleTimecode;
-  trackData.mNextSampleTime = nextSampleTime;
-  trackData.mNextGetSampleIndex = Some(i);
-
+  if (aFound) {
+    trackData.mNextSampleTimecode = nextSampleTimecode;
+    trackData.mNextSampleTime = nextSampleTime;
+    trackData.mNextGetSampleIndex = Some(i);
+  } else if (i > 0) {
+    // Go back to the previous keyframe or the original position so the next
+    // demux can succeed and be decoded.
+    for (int j = i - 1; j >= originalPos; i--) {
+      const RefPtr<MediaRawData>& sample = track[j];
+      if (sample->mKeyframe) {
+        trackData.mNextSampleTimecode =
+          TimeUnit::FromMicroseconds(sample->mTimecode);
+        trackData.mNextSampleTime = TimeUnit::FromMicroseconds(sample->mTime);
+        trackData.mNextGetSampleIndex = Some(uint32_t(j));
+        // We are unable to skip to a keyframe past aTimeThreshold, however
+        // we are speeding up decoding by dropping the unplayable frames.
+        // So we can mark aFound as true.
+        aFound = true;
+        break;
+      }
+      parsed--;
+    }
+  }
   return parsed;
 }
 
 const MediaRawData*
 TrackBuffersManager::GetSample(TrackInfo::TrackType aTrack,
                                size_t aIndex,
                                const TimeUnit& aExpectedDts,
                                const TimeUnit& aExpectedPts,