--- a/dom/media/encoder/MediaEncoder.cpp
+++ b/dom/media/encoder/MediaEncoder.cpp
@@ -331,17 +331,17 @@ MediaEncoder::EncodeData()
     if (NS_FAILED(rv)) {
       // Encoding might be canceled.
       LOG(LogLevel::Error, ("Error! Fail to get encoded data from video "
                             "encoder."));
       mState = ENCODE_ERROR;
       return rv;
     }
     for (uint32_t i = 0; i < encodedVideoData.GetEncodedFrames().Length(); i++) {
-      mEncodedVideoFrames.AppendElement(
+      mEncodedVideoFrames.Push(
         encodedVideoData.GetEncodedFrames().ElementAt(i));
     }
   }
 
   if (mAudioEncoder && !mAudioEncoder->IsEncodingComplete()) {
     EncodedFrameContainer encodedAudioData;
     rv = mAudioEncoder->GetEncodedTrack(encodedAudioData);
     if (NS_FAILED(rv)) {
@@ -354,67 +354,136 @@ MediaEncoder::EncodeData()
     for (uint32_t i = 0; i < encodedAudioData.GetEncodedFrames().Length(); i++) {
       RefPtr<EncodedFrame> frame =
         encodedAudioData.GetEncodedFrames().ElementAt(i);
       // Offset audio samples by appropriate amount. Do this before the mux
       // so we can ensure ordered timestamps.
       if (frame->mFrameType == EncodedFrame::FrameType::OPUS_AUDIO_FRAME) {
         frame->mTime += mAudioTimestampOffset;
       }
-      mEncodedAudioFrames.AppendElement(frame);
+      mEncodedAudioFrames.Push(frame);
     }
   }
   return rv;
 }
 
 nsresult
 MediaEncoder::WriteEncodedDataToMuxer()
 {
   PROFILER_LABEL("MediaEncoder", "WriteEncodedDataToMuxer",
     js::ProfileEntry::Category::OTHER);
 
   nsresult rv = NS_OK;
 
-  if(mVideoEncoder) {
+  // If we have both video and audio encoders, interleave the frames
+  if (mVideoEncoder && mAudioEncoder) {
+    EncodedFrameContainer encodedData;
+
+    // Interleave frames until we're out of audio or video
+    RefPtr<EncodedFrame> videoFrame;
+    RefPtr<EncodedFrame> audioFrame;
+    uint64_t expectedNextVideoTime = 0;
+    uint64_t expectedNextAudioTime = 0;
+    while (mEncodedVideoFrames.GetSize() > 0 &&
+      mEncodedAudioFrames.GetSize() > 0) {
+      videoFrame = mEncodedVideoFrames.PeekFront();
+      audioFrame = mEncodedAudioFrames.PeekFront();
+      // For any expected time our frames should occur at or after that time
+      MOZ_ASSERT(videoFrame->mTime >= expectedNextVideoTime);
+      MOZ_ASSERT(audioFrame->mTime >= expectedNextAudioTime);
+      if (videoFrame->mTime <= audioFrame->mTime) {
+        expectedNextVideoTime = videoFrame->GetEndTime();
+        encodedData.AppendEncodedFrame(mEncodedVideoFrames.PopFront().take());
+      } else {
+        expectedNextAudioTime = audioFrame->GetEndTime();
+        encodedData.AppendEncodedFrame(mEncodedAudioFrames.PopFront().take());
+      }
+    }
+
+    // If we're out of audio we still may be able to add more video...
+    if (mEncodedAudioFrames.GetSize() == 0) {
+      while (mEncodedVideoFrames.GetSize() > 0) {
+        videoFrame = mEncodedVideoFrames.PeekFront();
+        // If audio encoding is complete or if the video would precede the
+        // next audio sample we can add it
+        if (mAudioEncoder->IsEncodingComplete() ||
+          videoFrame->mTime < expectedNextAudioTime) {
+          encodedData.AppendEncodedFrame(
+            mEncodedVideoFrames.PopFront().take());
+        } else {
+          break;
+        }
+      }
+    }
+
+    // If we're out of video we still may be able to add more audio...
+    if (mEncodedVideoFrames.GetSize() == 0) {
+      while (mEncodedAudioFrames.GetSize() > 0) {
+        audioFrame = mEncodedAudioFrames.PeekFront();
+        // If video encoding is complete or if audio would precede the next
+        // video sample we can add it
+        if (mVideoEncoder->IsEncodingComplete() ||
+          audioFrame->mTime < expectedNextVideoTime) {
+          encodedData.AppendEncodedFrame(
+            mEncodedAudioFrames.PopFront().take());
+        } else {
+          break;
+        }
+      }
+    }
+
+    rv = mWriter->WriteEncodedTrack(encodedData, 0);
+    if (NS_FAILED(rv)) {
+      LOG(LogLevel::Error, ("Error! Fail to write encoded video + audio track "
+                            "to the media container."));
+      mState = ENCODE_ERROR;
+    }
+    return rv;
+  }
+
+  // If we reach here, we have only a single encoder and don't have to worry
+  // about any interleaving
+  if (mVideoEncoder) {
+    MOZ_ASSERT(!mAudioEncoder);
     EncodedFrameContainer encodedVideoData;
-    for (uint32_t i = 0; i < mEncodedVideoFrames.Length(); i++) {
-      encodedVideoData.AppendEncodedFrame(mEncodedVideoFrames.ElementAt(i));
+    while (mEncodedVideoFrames.GetSize() > 0) {
+      encodedVideoData.AppendEncodedFrame(
+        mEncodedVideoFrames.PopFront().take());
     }
-    mEncodedVideoFrames.Clear();
 
     rv = mWriter->WriteEncodedTrack(encodedVideoData,
                                     mVideoEncoder->IsEncodingComplete() ?
                                     ContainerWriter::END_OF_STREAM : 0);
     if (NS_FAILED(rv)) {
       LOG(LogLevel::Error, ("Error! Fail to write encoded video track to the "
                             "media container."));
       mState = ENCODE_ERROR;
-      return rv;
     }
   }
 
-  if(mAudioEncoder) {
+  if (mAudioEncoder) {
+    MOZ_ASSERT(!mVideoEncoder);
     EncodedFrameContainer encodedAudioData;
-    for (uint32_t i = 0; i < mEncodedAudioFrames.Length(); i++) {
-      encodedAudioData.AppendEncodedFrame(mEncodedAudioFrames.ElementAt(i));
+    while (mEncodedAudioFrames.GetSize() > 0) {
+      encodedAudioData.AppendEncodedFrame(
+        mEncodedAudioFrames.PopFront().take());
     }
-    mEncodedAudioFrames.Clear();
 
     rv = mWriter->WriteEncodedTrack(encodedAudioData,
                                     mAudioEncoder->IsEncodingComplete() ?
                                     ContainerWriter::END_OF_STREAM : 0);
     if (NS_FAILED(rv)) {
       LOG(LogLevel::Error, ("Error! Fail to write encoded audio track to the "
                             "media container."));
       mState = ENCODE_ERROR;
-      return rv;
     }
   }
 
   return rv;
+
 }
 
 nsresult
 MediaEncoder::CopyMetadataToMuxer(TrackEncoder *aTrackEncoder)
 {
   if (aTrackEncoder == nullptr) {
     return NS_OK;
   }

--- a/dom/media/encoder/MediaEncoder.h
+++ b/dom/media/encoder/MediaEncoder.h
@@ -12,16 +12,17 @@
 #include "CubebUtils.h"
 #include "MediaStreamGraph.h"
 #include "MediaStreamListener.h"
 #include "nsAutoPtr.h"
 #include "MediaStreamVideoSink.h"
 #include "nsIMemoryReporter.h"
 #include "mozilla/MemoryReporting.h"
 #include "mozilla/Atomics.h"
+#include "MediaQueue.h"
 
 namespace mozilla {
 
 class MediaStreamVideoRecorderSink : public MediaStreamVideoSink
 {
 public:
   explicit MediaStreamVideoRecorderSink(VideoTrackEncoder* aEncoder)
     : mVideoEncoder(aEncoder) {}
@@ -233,18 +234,18 @@ private:
   nsresult WriteEncodedDataToMuxer();
   // Get metadata from trackEncoder and copy to muxer
   nsresult CopyMetadataToMuxer(TrackEncoder* aTrackEncoder);
   // Process data pending in encoders
   nsresult EncodeData();
   nsAutoPtr<ContainerWriter> mWriter;
   nsAutoPtr<AudioTrackEncoder> mAudioEncoder;
   nsAutoPtr<VideoTrackEncoder> mVideoEncoder;
-  nsTArray<RefPtr<EncodedFrame>> mEncodedAudioFrames;
-  nsTArray<RefPtr<EncodedFrame>> mEncodedVideoFrames;
+  MediaQueue<EncodedFrame> mEncodedAudioFrames;
+  MediaQueue<EncodedFrame> mEncodedVideoFrames;
   // How much each audio time stamp should be shifted forward in time. Used to
   // adjust for opus codec delay.
   uint64_t mAudioTimestampOffset = 0;
   RefPtr<MediaStreamVideoRecorderSink> mVideoSink;
   TimeStamp mStartTime;
   nsString mMIMEType;
   int64_t mSizeOfBuffer;
   int mState;