--- a/dom/media/fmp4/MP4Demuxer.cpp
+++ b/dom/media/fmp4/MP4Demuxer.cpp
@@ -405,20 +405,31 @@ RefPtr<MP4TrackDemuxer::SeekPromise>
 MP4TrackDemuxer::Seek(const media::TimeUnit& aTime)
 {
   auto seekTime = aTime;
   mQueuedSample = nullptr;
 
   mIterator->Seek(seekTime.ToMicroseconds());
 
   // Check what time we actually seeked to.
-  mQueuedSample = GetNextSample();
-  if (mQueuedSample) {
-    seekTime = mQueuedSample->mTime;
-  }
+  do {
+    RefPtr<MediaRawData> sample = GetNextSample();
+    if (!sample) {
+      return SeekPromise::CreateAndReject(NS_ERROR_DOM_MEDIA_END_OF_STREAM,
+                                          __func__);
+    }
+    if (!sample->Size()) {
+      // This sample can't be decoded, continue searching.
+      continue;
+    }
+    if (sample->mKeyframe) {
+      mQueuedSample = sample;
+      seekTime = mQueuedSample->mTime;
+    }
+  } while (!mQueuedSample);
 
   SetNextKeyFrameTime();
 
   return SeekPromise::CreateAndResolve(seekTime, __func__);
 }
 
 already_AddRefed<MediaRawData>
 MP4TrackDemuxer::GetNextSample()