--- a/dom/media/MediaDecoderStateMachine.cpp
+++ b/dom/media/MediaDecoderStateMachine.cpp
@@ -216,16 +216,22 @@ public:
 
   virtual bool HandleVideoDecoded(MediaData* aVideo, TimeStamp aDecodeStart)
   {
     return false;
   }
 
   virtual bool HandleEndOfStream() { return false; }
 
+  virtual RefPtr<MediaDecoder::SeekPromise> HandleSeek(SeekTarget aTarget)
+  {
+    MOZ_ASSERT(false, "Can't seek in this state");
+    return nullptr;
+  }
+
 protected:
   using Master = MediaDecoderStateMachine;
   explicit StateObject(Master* aPtr) : mMaster(aPtr) {}
   TaskQueue* OwnerThread() const { return mMaster->mTaskQueue; }
   MediaResource* Resource() const { return mMaster->mResource; }
   MediaDecoderReaderWrapper* Reader() const { return mMaster->mReader; }
 
   // Note this function will delete the current state object.
@@ -371,16 +377,24 @@ public:
     return DECODER_STATE_WAIT_FOR_CDM;
   }
 
   bool HandleCDMProxyReady() override
   {
     SetState(DECODER_STATE_DECODING_FIRSTFRAME);
     return true;
   }
+
+  RefPtr<MediaDecoder::SeekPromise> HandleSeek(SeekTarget aTarget) override
+  {
+    SLOG("Not Enough Data to seek at this stage, queuing seek");
+    mMaster->mQueuedSeek.RejectIfExists(__func__);
+    mMaster->mQueuedSeek.mTarget = aTarget;
+    return mMaster->mQueuedSeek.mPromise.Ensure(__func__);
+  }
 };
 
 class MediaDecoderStateMachine::DormantState
   : public MediaDecoderStateMachine::StateObject
 {
 public:
   explicit DormantState(Master* aPtr) : StateObject(aPtr) {}
 
@@ -402,16 +416,24 @@ public:
   bool HandleDormant(bool aDormant) override
   {
     if (!aDormant) {
       // Exit dormant state.
       SetState(DECODER_STATE_DECODING_METADATA);
     }
     return true;
   }
+
+  RefPtr<MediaDecoder::SeekPromise> HandleSeek(SeekTarget aTarget) override
+  {
+    SLOG("Not Enough Data to seek at this stage, queuing seek");
+    mMaster->mQueuedSeek.RejectIfExists(__func__);
+    mMaster->mQueuedSeek.mTarget = aTarget;
+    return mMaster->mQueuedSeek.mPromise.Ensure(__func__);
+  }
 };
 
 class MediaDecoderStateMachine::DecodingFirstFrameState
   : public MediaDecoderStateMachine::StateObject
 {
 public:
   explicit DecodingFirstFrameState(Master* aPtr) : StateObject(aPtr) {}
 
@@ -455,16 +477,36 @@ public:
   }
 
   bool HandleEndOfStream() override
   {
     MaybeFinishDecodeFirstFrame();
     return true;
   }
 
+  RefPtr<MediaDecoder::SeekPromise> HandleSeek(SeekTarget aTarget) override
+  {
+    // Should've transitioned to DECODING in Enter()
+    // if mSentFirstFrameLoadedEvent is true.
+    MOZ_ASSERT(!mMaster->mSentFirstFrameLoadedEvent);
+
+    if (!Reader()->ForceZeroStartTime()) {
+      SLOG("Not Enough Data to seek at this stage, queuing seek");
+      mMaster->mQueuedSeek.RejectIfExists(__func__);
+      mMaster->mQueuedSeek.mTarget = aTarget;
+      return mMaster->mQueuedSeek.mPromise.Ensure(__func__);
+    }
+
+    mMaster->mQueuedSeek.RejectIfExists(__func__);
+    SLOG("Changed state to SEEKING (to %lld)", aTarget.GetTime().ToMicroseconds());
+    SeekJob seekJob;
+    seekJob.mTarget = aTarget;
+    return mMaster->InitiateSeek(Move(seekJob));
+  }
+
 private:
   // Notify FirstFrameLoaded if having decoded first frames and
   // transition to SEEKING if there is any pending seek, or DECODING otherwise.
   void MaybeFinishDecodeFirstFrame()
   {
     MOZ_ASSERT(!mMaster->mSentFirstFrameLoadedEvent);
 
     if ((mMaster->IsAudioDecoding() && mMaster->AudioQueue().GetSize() == 0) ||
@@ -556,16 +598,25 @@ public:
   bool HandleVideoDecoded(MediaData* aVideo, TimeStamp aDecodeStart) override
   {
     mMaster->Push(aVideo, MediaData::VIDEO_DATA);
     mMaster->MaybeStopPrerolling();
     CheckSlowDecoding(aDecodeStart);
     return true;
   }
 
+  RefPtr<MediaDecoder::SeekPromise> HandleSeek(SeekTarget aTarget) override
+  {
+    mMaster->mQueuedSeek.RejectIfExists(__func__);
+    SLOG("Changed state to SEEKING (to %lld)", aTarget.GetTime().ToMicroseconds());
+    SeekJob seekJob;
+    seekJob.mTarget = aTarget;
+    return mMaster->InitiateSeek(Move(seekJob));
+  }
+
 private:
   void CheckSlowDecoding(TimeStamp aDecodeStart)
   {
     // For non async readers, if the requested video sample was slow to
     // arrive, increase the amount of audio we buffer to ensure that we
     // don't run out of audio. This is unnecessary for async readers,
     // since they decode audio and video on different threads so they
     // are unlikely to run out of decoded audio.
@@ -642,16 +693,25 @@ public:
     return true;
   }
 
   bool HandleVideoDecoded(MediaData* aVideo, TimeStamp aDecodeStart) override
   {
     MOZ_ASSERT(false);
     return true;
   }
+
+  RefPtr<MediaDecoder::SeekPromise> HandleSeek(SeekTarget aTarget) override
+  {
+    mMaster->mQueuedSeek.RejectIfExists(__func__);
+    SLOG("Changed state to SEEKING (to %lld)", aTarget.GetTime().ToMicroseconds());
+    SeekJob seekJob;
+    seekJob.mTarget = aTarget;
+    return mMaster->InitiateSeek(Move(seekJob));
+  }
 };
 
 class MediaDecoderStateMachine::BufferingState
   : public MediaDecoderStateMachine::StateObject
 {
 public:
   explicit BufferingState(Master* aPtr) : StateObject(aPtr) {}
 
@@ -743,16 +803,25 @@ public:
       SetState(DECODER_STATE_COMPLETED);
     } else {
       // Check if we can exit buffering.
       mMaster->ScheduleStateMachine();
     }
     return true;
   }
 
+  RefPtr<MediaDecoder::SeekPromise> HandleSeek(SeekTarget aTarget) override
+  {
+    mMaster->mQueuedSeek.RejectIfExists(__func__);
+    SLOG("Changed state to SEEKING (to %lld)", aTarget.GetTime().ToMicroseconds());
+    SeekJob seekJob;
+    seekJob.mTarget = aTarget;
+    return mMaster->InitiateSeek(Move(seekJob));
+  }
+
 private:
   TimeStamp mBufferingStart;
 };
 
 class MediaDecoderStateMachine::CompletedState
   : public MediaDecoderStateMachine::StateObject
 {
 public:
@@ -811,16 +880,25 @@ public:
     }
   }
 
   State GetState() const override
   {
     return DECODER_STATE_COMPLETED;
   }
 
+  RefPtr<MediaDecoder::SeekPromise> HandleSeek(SeekTarget aTarget) override
+  {
+    mMaster->mQueuedSeek.RejectIfExists(__func__);
+    SLOG("Changed state to SEEKING (to %lld)", aTarget.GetTime().ToMicroseconds());
+    SeekJob seekJob;
+    seekJob.mTarget = aTarget;
+    return mMaster->InitiateSeek(Move(seekJob));
+  }
+
 private:
   bool mSentPlaybackEndedEvent = false;
 };
 
 class MediaDecoderStateMachine::ShutdownState
   : public MediaDecoderStateMachine::StateObject
 {
 public:
@@ -1937,34 +2015,17 @@ MediaDecoderStateMachine::Seek(SeekTarge
 
   if (aTarget.IsNextFrame() && !HasVideo()) {
     DECODER_WARN("Ignore a NextFrameSeekTask on a media file without video track.");
     return MediaDecoder::SeekPromise::CreateAndReject(/* aIgnored = */ true, __func__);
   }
 
   MOZ_ASSERT(mDuration.Ref().isSome(), "We should have got duration already");
 
-  // Can't seek until the start time is known.
-  bool hasStartTime = mSentFirstFrameLoadedEvent || mReader->ForceZeroStartTime();
-  // Can't seek when state is WAIT_FOR_CDM or DORMANT.
-  bool stateAllowed = mState >= DECODER_STATE_DECODING_FIRSTFRAME;
-
-  if (!stateAllowed || !hasStartTime) {
-    DECODER_LOG("Seek() Not Enough Data to continue at this stage, queuing seek");
-    mQueuedSeek.RejectIfExists(__func__);
-    mQueuedSeek.mTarget = aTarget;
-    return mQueuedSeek.mPromise.Ensure(__func__);
-  }
-  mQueuedSeek.RejectIfExists(__func__);
-
-  DECODER_LOG("Changed state to SEEKING (to %lld)", aTarget.GetTime().ToMicroseconds());
-
-  SeekJob seekJob;
-  seekJob.mTarget = aTarget;
-  return InitiateSeek(Move(seekJob));
+  return mStateObj->HandleSeek(aTarget);
 }
 
 RefPtr<MediaDecoder::SeekPromise>
 MediaDecoderStateMachine::InvokeSeek(SeekTarget aTarget)
 {
   return InvokeAsync(OwnerThread(), this, __func__,
                      &MediaDecoderStateMachine::Seek, aTarget);
 }