--- a/dom/animation/EffectCompositor.cpp
+++ b/dom/animation/EffectCompositor.cpp
@@ -12,16 +12,17 @@
 #include "mozilla/AnimationComparator.h"
 #include "mozilla/AnimationPerformanceWarning.h"
 #include "mozilla/AnimationTarget.h"
 #include "mozilla/AnimationUtils.h"
 #include "mozilla/EffectSet.h"
 #include "mozilla/LayerAnimationInfo.h"
 #include "mozilla/RestyleManager.h"
 #include "mozilla/RestyleManagerInlines.h"
+#include "mozilla/ServoStyleSet.h"
 #include "mozilla/StyleAnimationValue.h"
 #include "nsComputedDOMStyle.h" // nsComputedDOMStyle::GetPresShellForContent
 #include "nsCSSPseudoElements.h"
 #include "nsCSSPropertyIDSet.h"
 #include "nsCSSProps.h"
 #include "nsIAtom.h"
 #include "nsIPresShell.h"
 #include "nsIPresShellInlines.h"
@@ -308,21 +309,38 @@ EffectCompositor::PostRestyleForAnimatio
   if (!element) {
     return;
   }
 
   nsRestyleHint hint = aCascadeLevel == CascadeLevel::Transitions ?
                                         eRestyle_CSSTransitions :
                                         eRestyle_CSSAnimations;
 
-  // FIXME: stylo only supports Self and Subtree hints now, so we override it
-  // for stylo if we are not in process of restyling.
-  if (mPresContext->StyleSet()->IsServo() &&
-      !mPresContext->RestyleManager()->IsInStyleRefresh()) {
-    hint = eRestyle_Self | eRestyle_Subtree;
+  if (mPresContext->StyleSet()->IsServo()) {
+    MOZ_ASSERT(NS_IsMainThread(),
+               "Restyle request during restyling should be requested only on "
+               "the main-thread. e.g. after the parallel traversal");
+    if (ServoStyleSet::IsInServoTraversal()) {
+      // FIXME: Bug 1302946: We will handle eRestyle_CSSTransitions.
+      MOZ_ASSERT(hint == eRestyle_CSSAnimations);
+
+      // We can't call Servo_NoteExplicitHints here since AtomicRefCell does not
+      // allow us mutate ElementData of the |aElement| in SequentialTask.
+      // Instead we call Servo_NoteExplicitHints for the element in PreTraverse() right
+      // which will be called right before the second traversal that we do for
+      // updating CSS animations.
+      // In that case PreTraverse() will return true so that we know to do the
+      // second traversal so we don't need to post any restyle requests to the
+      // PresShell.
+      return;
+    } else if (!mPresContext->RestyleManager()->IsInStyleRefresh()) {
+      // FIXME: stylo only supports Self and Subtree hints now, so we override
+      // it for stylo if we are not in process of restyling.
+      hint = eRestyle_Self | eRestyle_Subtree;
+    }
   }
   mPresContext->PresShell()->RestyleForAnimation(element, hint);
 }
 
 void
 EffectCompositor::PostRestyleForThrottledAnimations()
 {
   for (size_t i = 0; i < kCascadeLevelCount; i++) {
@@ -927,48 +945,60 @@ EffectCompositor::SetPerformanceWarning(
     return;
   }
 
   for (KeyframeEffectReadOnly* effect : *effects) {
     effect->SetPerformanceWarning(aProperty, aWarning);
   }
 }
 
-void
+bool
 EffectCompositor::PreTraverse()
 {
   MOZ_ASSERT(NS_IsMainThread());
   MOZ_ASSERT(mPresContext->RestyleManager()->IsServo());
 
+  bool foundElementsNeedingRestyle = false;
   for (auto& elementsToRestyle : mElementsToRestyle) {
     for (auto iter = elementsToRestyle.Iter(); !iter.Done(); iter.Next()) {
       bool postedRestyle = iter.Data();
       // Ignore throttled restyle.
       if (!postedRestyle) {
         continue;
       }
 
       NonOwningAnimationTarget target = iter.Key();
+
+      // We need to post restyle hints even if the target is not in EffectSet to
+      // ensure the final restyling for removed animations.
+      // We can't call PostRestyleEvent directly here since we are still in the
+      // middle of the servo traversal.
+      mPresContext->RestyleManager()->AsServo()->
+        PostRestyleEventForAnimations(target.mElement,
+                                      eRestyle_Self | eRestyle_Subtree);
+      foundElementsNeedingRestyle = true;
+
       EffectSet* effects =
         EffectSet::GetEffectSet(target.mElement, target.mPseudoType);
       if (!effects) {
-        // Drop the EffectSets that have been destroyed.
+        // Drop EffectSets that have been destroyed.
         iter.Remove();
         continue;
       }
 
       for (KeyframeEffectReadOnly* effect : *effects) {
         effect->GetAnimation()->WillComposeStyle();
       }
 
       // Remove the element from the list of elements to restyle since we are
       // about to restyle it.
       iter.Remove();
     }
   }
+  return foundElementsNeedingRestyle;
 }
 
 void
 EffectCompositor::PreTraverse(dom::Element* aElement, nsIAtom* aPseudoTagOrNull)
 {
   MOZ_ASSERT(NS_IsMainThread());
   MOZ_ASSERT(mPresContext->RestyleManager()->IsServo());
 

--- a/dom/animation/EffectCompositor.h
+++ b/dom/animation/EffectCompositor.h
@@ -224,17 +224,18 @@ public:
   static void SetPerformanceWarning(
     const nsIFrame* aFrame,
     nsCSSPropertyID aProperty,
     const AnimationPerformanceWarning& aWarning);
 
   // Do a bunch of stuff that we should avoid doing during the parallel
   // traversal (e.g. changing member variables) for all elements that we expect
   // to restyle on the next traversal.
-  void PreTraverse();
+  // Returns true if there are elements needing a restyle for animation.
+  bool PreTraverse();
 
   // Similar to the above but only for the (pseudo-)element.
   void PreTraverse(dom::Element* aElement, nsIAtom* aPseudoTagOrNull);
 
 private:
   ~EffectCompositor() = default;
 
   // Rebuilds the animation rule corresponding to |aCascadeLevel| on the

--- a/layout/base/ServoRestyleManager.cpp
+++ b/layout/base/ServoRestyleManager.cpp
@@ -74,16 +74,23 @@ ServoRestyleManager::PostRestyleEvent(El
 
   if (aRestyleHint || aMinChangeHint) {
     Servo_NoteExplicitHints(aElement, aRestyleHint, aMinChangeHint);
   }
 
   PostRestyleEventInternal(false);
 }
 
+/* static */ void
+ServoRestyleManager::PostRestyleEventForAnimations(Element* aElement,
+                                                   nsRestyleHint aRestyleHint)
+{
+  Servo_NoteExplicitHints(aElement, aRestyleHint, nsChangeHint(0));
+}
+
 void
 ServoRestyleManager::RebuildAllStyleData(nsChangeHint aExtraHint,
                                          nsRestyleHint aRestyleHint)
 {
   // TODO(emilio, bz): We probably need to do some actual restyling here too.
   NS_WARNING("stylo: ServoRestyleManager::RebuildAllStyleData is incomplete");
   StyleSet()->RebuildData();
 }

--- a/layout/base/ServoRestyleManager.h
+++ b/layout/base/ServoRestyleManager.h
@@ -87,16 +87,27 @@ public:
                                          nsIAtom* aPseudoTagOrNull);
 
   /**
    * Clears the ServoElementData and HasDirtyDescendants from all elements
    * in the subtree rooted at aElement.
    */
   static void ClearServoDataFromSubtree(Element* aElement);
 
+  /**
+   * Posts restyle hints for animations.
+   * This is only called for the second traversal for CSS animations during
+   * updating CSS animations in a SequentialTask.
+   * This function does neither register a refresh observer nor flag that a
+   * style flush is needed since this function is supposed to be called during
+   * restyling process and this restyle event will be processed in the second
+   * traversal of the same restyling process.
+   */
+  static void PostRestyleEventForAnimations(dom::Element* aElement,
+                                            nsRestyleHint aRestyleHint);
 protected:
   ~ServoRestyleManager() override
   {
     MOZ_ASSERT(!mReentrantChanges);
   }
 
 private:
   /**

--- a/layout/style/ServoStyleSet.cpp
+++ b/layout/style/ServoStyleSet.cpp
@@ -219,16 +219,24 @@ ServoStyleSet::PrepareAndTraverseSubtree
   // calling into the (potentially-parallel) Servo traversal, where a cache hit
   // is necessary to avoid a data race when updating the cache.
   mozilla::Unused << aRoot->OwnerDoc()->GetRootElement();
 
   MOZ_ASSERT(!sInServoTraversal);
   sInServoTraversal = true;
   bool postTraversalRequired =
     Servo_TraverseSubtree(aRoot, mRawSet.get(), aRootBehavior);
+
+  // If there are still animation restyles needed, trigger a second traversal to
+  // update CSS animations' styles.
+  if (mPresContext->EffectCompositor()->PreTraverse() &&
+      Servo_TraverseSubtree(aRoot, mRawSet.get(), aRootBehavior)) {
+    postTraversalRequired = true;
+  }
+
   sInServoTraversal = false;
   return postTraversalRequired;
 }
 
 already_AddRefed<nsStyleContext>
 ServoStyleSet::ResolveStyleFor(Element* aElement,
                                nsStyleContext* aParentContext,
                                LazyComputeBehavior aMayCompute,