--- a/dom/media/MediaFormatReader.cpp
+++ b/dom/media/MediaFormatReader.cpp
@@ -727,20 +727,60 @@ MediaFormatReader::OnDemuxerInitDone(nsr
   mInfo.mMediaSeekableOnlyInBufferedRanges =
     mDemuxer->IsSeekableOnlyInBufferedRanges();
 
   if (!videoActive && !audioActive) {
     mMetadataPromise.Reject(NS_ERROR_DOM_MEDIA_METADATA_ERR, __func__);
     return;
   }
 
+  mTags = Move(tags);
   mInitDone = true;
+
+  // Try to get the start time.
+  // For MSE case, the start time of each track is assumed to be 0.
+  // For others, we must demux the first sample to know the start time for each
+  // track.
+  if (ForceZeroStartTime()) {
+    mAudio.mFirstDemuxedSampleTime.emplace(TimeUnit::FromMicroseconds(0));
+    mVideo.mFirstDemuxedSampleTime.emplace(TimeUnit::FromMicroseconds(0));
+  } else {
+    if (HasAudio()) {
+      RequestDemuxSamples(TrackInfo::kAudioTrack);
+    }
+
+    if (HasVideo()) {
+      RequestDemuxSamples(TrackInfo::kVideoTrack);
+    }
+  }
+
+  MaybeResolveMetadataPromise();
+}
+
+void
+MediaFormatReader::MaybeResolveMetadataPromise()
+{
+  MOZ_ASSERT(OnTaskQueue());
+
+  if ((HasAudio() && mAudio.mFirstDemuxedSampleTime.isNothing()) ||
+      (HasVideo() && mVideo.mFirstDemuxedSampleTime.isNothing())) {
+    return;
+  }
+
+  TimeUnit startTime =
+    std::min(mAudio.mFirstDemuxedSampleTime.refOr(TimeUnit::FromInfinity()),
+             mVideo.mFirstDemuxedSampleTime.refOr(TimeUnit::FromInfinity()));
+
+  if (!startTime.IsInfinite()) {
+    mInfo.mStartTime = startTime; // mInfo.mStartTime is initialized to 0.
+  }
+
   RefPtr<MetadataHolder> metadata = new MetadataHolder();
   metadata->mInfo = mInfo;
-  metadata->mTags = tags->Count() ? tags.release() : nullptr;
+  metadata->mTags = mTags->Count() ? mTags.release() : nullptr;
   mMetadataPromise.Resolve(metadata, __func__);
 }
 
 bool
 MediaFormatReader::IsEncrypted() const
 {
   return (HasAudio() && mInfo.mAudio.mCrypto.mValid) ||
          (HasVideo() && mInfo.mVideo.mCrypto.mValid);
@@ -858,20 +898,32 @@ MediaFormatReader::OnDemuxFailed(TrackTy
       NotifyError(aTrack, aError);
       break;
   }
 }
 
 void
 MediaFormatReader::DoDemuxVideo()
 {
-  mVideo.mDemuxRequest.Begin(mVideo.mTrackDemuxer->GetSamples(1)
-                      ->Then(OwnerThread(), __func__, this,
-                             &MediaFormatReader::OnVideoDemuxCompleted,
-                             &MediaFormatReader::OnVideoDemuxFailed));
+  auto p = mVideo.mTrackDemuxer->GetSamples(1);
+
+  if (mVideo.mFirstDemuxedSampleTime.isNothing()) {
+    RefPtr<MediaFormatReader> self = this;
+    p = p->Then(OwnerThread(), __func__,
+                [self] (RefPtr<MediaTrackDemuxer::SamplesHolder> aSamples) {
+                  self->OnFirstDemuxCompleted(TrackInfo::kVideoTrack, aSamples);
+                },
+                [self] (const MediaResult& aError) {
+                  self->OnFirstDemuxFailed(TrackInfo::kVideoTrack, aError);
+                })->CompletionPromise();
+  }
+
+  mVideo.mDemuxRequest.Begin(p->Then(OwnerThread(), __func__, this,
+                                     &MediaFormatReader::OnVideoDemuxCompleted,
+                                     &MediaFormatReader::OnVideoDemuxFailed));
 }
 
 void
 MediaFormatReader::OnVideoDemuxCompleted(RefPtr<MediaTrackDemuxer::SamplesHolder> aSamples)
 {
   LOGV("%d video samples demuxed (sid:%d)",
        aSamples->mSamples.Length(),
        aSamples->mSamples[0]->mTrackInfo ? aSamples->mSamples[0]->mTrackInfo->GetID() : 0);
@@ -912,20 +964,32 @@ MediaFormatReader::RequestAudioData()
   ScheduleUpdate(TrackInfo::kAudioTrack);
 
   return p;
 }
 
 void
 MediaFormatReader::DoDemuxAudio()
 {
-  mAudio.mDemuxRequest.Begin(mAudio.mTrackDemuxer->GetSamples(1)
-                      ->Then(OwnerThread(), __func__, this,
-                             &MediaFormatReader::OnAudioDemuxCompleted,
-                             &MediaFormatReader::OnAudioDemuxFailed));
+  auto p = mAudio.mTrackDemuxer->GetSamples(1);
+
+  if (mAudio.mFirstDemuxedSampleTime.isNothing()) {
+    RefPtr<MediaFormatReader> self = this;
+    p = p->Then(OwnerThread(), __func__,
+                [self] (RefPtr<MediaTrackDemuxer::SamplesHolder> aSamples) {
+                  self->OnFirstDemuxCompleted(TrackInfo::kAudioTrack, aSamples);
+                },
+                [self] (const MediaResult& aError) {
+                  self->OnFirstDemuxFailed(TrackInfo::kAudioTrack, aError);
+                })->CompletionPromise();
+  }
+
+  mAudio.mDemuxRequest.Begin(p->Then(OwnerThread(), __func__, this,
+                                     &MediaFormatReader::OnAudioDemuxCompleted,
+                                     &MediaFormatReader::OnAudioDemuxFailed));
 }
 
 void
 MediaFormatReader::OnAudioDemuxCompleted(RefPtr<MediaTrackDemuxer::SamplesHolder> aSamples)
 {
   LOGV("%d audio samples demuxed (sid:%d)",
        aSamples->mSamples.Length(),
        aSamples->mSamples[0]->mTrackInfo ? aSamples->mSamples[0]->mTrackInfo->GetID() : 0);
@@ -1199,21 +1263,16 @@ MediaFormatReader::HandleDemuxedSamples(
     return;
   }
 
   if (!decoder.mDecoder) {
     mDecoderFactory->CreateDecoder(aTrack);
     return;
   }
 
-  if (!ForceZeroStartTime() && decoder.mFirstDemuxedSampleTime.isNothing()) {
-    decoder.mFirstDemuxedSampleTime.emplace(
-      media::TimeUnit::FromMicroseconds(decoder.mQueuedSamples[0]->mTime));
-  }
-
   LOGV("Giving %s input to decoder", TrackTypeToStr(aTrack));
 
   // Decode all our demuxed frames.
   bool samplesPending = false;
   while (decoder.mQueuedSamples.Length()) {
     RefPtr<MediaRawData> sample = decoder.mQueuedSamples[0];
     RefPtr<SharedTrackInfo> info = sample->mTrackInfo;
 
@@ -2335,9 +2394,42 @@ MediaFormatReader::SetBlankDecode(TrackT
   decoder.mIsBlankDecode = aIsBlankDecode;
   decoder.Flush();
   decoder.ShutdownDecoder();
   ScheduleUpdate(TrackInfo::kVideoTrack);
 
   return;
 }
 
+void
+MediaFormatReader::OnFirstDemuxCompleted(TrackInfo::TrackType aType,
+                                         RefPtr<MediaTrackDemuxer::SamplesHolder> aSamples)
+{
+  MOZ_ASSERT(OnTaskQueue());
+
+  if (mShutdown) {
+    return;
+  }
+
+  auto& decoder = GetDecoderData(aType);
+  MOZ_ASSERT(decoder.mFirstDemuxedSampleTime.isNothing());
+  decoder.mFirstDemuxedSampleTime.emplace(
+    TimeUnit::FromMicroseconds(aSamples->mSamples[0]->mTime));
+  MaybeResolveMetadataPromise();
+}
+
+void
+MediaFormatReader::OnFirstDemuxFailed(TrackInfo::TrackType aType,
+                                      const MediaResult& aError)
+{
+  MOZ_ASSERT(OnTaskQueue());
+
+  if (mShutdown) {
+    return;
+  }
+
+  auto& decoder = GetDecoderData(aType);
+  MOZ_ASSERT(decoder.mFirstDemuxedSampleTime.isNothing());
+  decoder.mFirstDemuxedSampleTime.emplace(TimeUnit::FromInfinity());
+  MaybeResolveMetadataPromise();
+}
+
 } // namespace mozilla

--- a/dom/media/MediaFormatReader.h
+++ b/dom/media/MediaFormatReader.h
@@ -590,13 +590,22 @@ private:
   RefPtr<GMPCrashHelper> mCrashHelper;
 
   void SetBlankDecode(TrackType aTrack, bool aIsBlankDecode);
 
   class DecoderFactory;
   UniquePtr<DecoderFactory> mDecoderFactory;
 
   MediaEventListener mCompositorUpdatedListener;
+
+  void OnFirstDemuxCompleted(TrackInfo::TrackType aType,
+                             RefPtr<MediaTrackDemuxer::SamplesHolder> aSamples);
+
+  void OnFirstDemuxFailed(TrackInfo::TrackType aType, const MediaResult& aError);
+
+  void MaybeResolveMetadataPromise();
+
+  UniquePtr<MetadataTags> mTags;
 };
 
 } // namespace mozilla
 
 #endif

--- a/dom/media/MediaInfo.h
+++ b/dom/media/MediaInfo.h
@@ -498,16 +498,20 @@ public:
 
   // True if the media is seekable (i.e. supports random access).
   bool mMediaSeekable = true;
 
   // True if the media is only seekable within its buffered ranges.
   bool mMediaSeekableOnlyInBufferedRanges = false;
 
   EncryptionInfo mCrypto;
+
+  // The minimum of start times of audio and video tracks.
+  // Use to map the zero time on the media timeline to the first frame.
+  media::TimeUnit mStartTime;
 };
 
 class SharedTrackInfo {
   NS_INLINE_DECL_THREADSAFE_REFCOUNTING(SharedTrackInfo)
 public:
   SharedTrackInfo(const TrackInfo& aOriginal, uint32_t aStreamID)
     : mInfo(aOriginal.Clone())
     , mStreamSourceID(aStreamID)