--- a/dom/media/mediasource/TrackBuffersManager.cpp
+++ b/dom/media/mediasource/TrackBuffersManager.cpp
@@ -1619,16 +1619,22 @@ TrackBuffersManager::InsertFrames(TrackB
 
   // 15. Remove decoding dependencies of the coded frames removed in the previous step:
   // Remove all coded frames between the coded frames removed in the previous step and the next random access point after those removed frames.
 
   TimeIntervals intersection = trackBuffer.mBufferedRanges;
   intersection.Intersection(aIntervals);
 
   if (intersection.Length()) {
+    if (aSamples[0]->mKeyframe) {
+      // We are starting a new GOP, we do not have to worry about breaking an
+      // existing current coded frame group. Reset the next insertion index
+      // so the search for when to start our frames removal can be exhaustive.
+      trackBuffer.mNextInsertionIndex.reset();
+    }
     RemoveFrames(aIntervals, trackBuffer, trackBuffer.mNextInsertionIndex.refOr(0));
   }
 
   // 16. Add the coded frame with the presentation timestamp, decode timestamp, and frame duration to the track buffer.
   if (!CheckNextInsertionIndex(aTrackData,
                                TimeUnit::FromMicroseconds(aSamples[0]->mTime))) {
     RejectProcessing(NS_ERROR_FAILURE, __func__);
     return;