diff --git a/update_manager/evaluation_context.cc b/update_manager/evaluation_context.cc
index 04bc3ee..5bee226 100644
--- a/update_manager/evaluation_context.cc
+++ b/update_manager/evaluation_context.cc
@@ -14,6 +14,7 @@
 
 #include "update_engine/utils.h"
 
+using base::Callback;
 using base::Closure;
 using base::Time;
 using base::TimeDelta;
@@ -47,12 +48,15 @@
 
 namespace chromeos_update_manager {
 
-EvaluationContext::EvaluationContext(ClockInterface* clock,
-                                     TimeDelta evaluation_timeout,
-                                     TimeDelta expiration_timeout)
+EvaluationContext::EvaluationContext(
+    ClockInterface* clock,
+    TimeDelta evaluation_timeout,
+    TimeDelta expiration_timeout,
+    scoped_ptr<Callback<void(EvaluationContext*)>> unregister_cb)
     : clock_(clock),
       evaluation_timeout_(evaluation_timeout),
       expiration_timeout_(expiration_timeout),
+      unregister_cb_(unregister_cb.Pass()),
       weak_ptr_factory_(this) {
   ResetEvaluation();
   ResetExpiration();
@@ -60,15 +64,19 @@
 
 EvaluationContext::~EvaluationContext() {
   RemoveObserversAndTimeout();
+  if (unregister_cb_.get())
+    unregister_cb_->Run(this);
 }
 
-void EvaluationContext::RemoveObserversAndTimeout() {
+scoped_ptr<Closure> EvaluationContext::RemoveObserversAndTimeout() {
   for (auto& it : value_cache_) {
     if (it.first->GetMode() == kVariableModeAsync)
       it.first->RemoveObserver(this);
   }
   CancelMainLoopEvent(timeout_event_);
   timeout_event_ = kEventIdNull;
+
+  return scoped_ptr<Closure>(callback_.release());
 }
 
 TimeDelta EvaluationContext::RemainingTime(Time monotonic_deadline) const {
@@ -97,10 +105,8 @@
 }
 
 void EvaluationContext::OnValueChangedOrTimeout() {
-  RemoveObserversAndTimeout();
-
   // Copy the callback handle locally, allowing it to be reassigned.
-  scoped_ptr<Closure> callback(callback_.release());
+  scoped_ptr<Closure> callback = RemoveObserversAndTimeout();
 
   if (callback.get())
     callback->Run();
diff --git a/update_manager/evaluation_context.h b/update_manager/evaluation_context.h
index 81574d4..e743669 100644
--- a/update_manager/evaluation_context.h
+++ b/update_manager/evaluation_context.h
@@ -8,6 +8,7 @@
 #include <map>
 #include <string>
 
+#include <base/bind.h>
 #include <base/callback.h>
 #include <base/memory/ref_counted.h>
 #include <base/memory/scoped_ptr.h>
@@ -52,12 +53,16 @@
 class EvaluationContext : public base::RefCounted<EvaluationContext>,
                           private BaseVariable::ObserverInterface {
  public:
-  EvaluationContext(chromeos_update_engine::ClockInterface* clock,
-                    base::TimeDelta evaluation_timeout,
-                    base::TimeDelta expiration_timeout);
+  EvaluationContext(
+      chromeos_update_engine::ClockInterface* clock,
+      base::TimeDelta evaluation_timeout,
+      base::TimeDelta expiration_timeout,
+      scoped_ptr<base::Callback<void(EvaluationContext*)>> unregister_cb);
   EvaluationContext(chromeos_update_engine::ClockInterface* clock,
                     base::TimeDelta evaluation_timeout)
-      : EvaluationContext(clock, evaluation_timeout, base::TimeDelta::Max()) {}
+      : EvaluationContext(
+          clock, evaluation_timeout, base::TimeDelta::Max(),
+          scoped_ptr<base::Callback<void(EvaluationContext*)>>()) {}
   ~EvaluationContext();
 
   // Returns a pointer to the value returned by the passed variable |var|. The
@@ -105,13 +110,14 @@
   // to help with debugging and the format may change in the future.
   std::string DumpContext() const;
 
+  // Removes all the Observers callbacks and timeout events scheduled by
+  // RunOnValueChangeOrTimeout(). Also releases and returns the closure
+  // associated with these events. This method is idempotent.
+  scoped_ptr<base::Closure> RemoveObserversAndTimeout();
+
  private:
   friend class UmEvaluationContextTest;
 
-  // Removes all the Observers and timeout callbacks scheduled by
-  // RunOnValueChangeOrTimeout(). This method is idempotent.
-  void RemoveObserversAndTimeout();
-
   // BaseVariable::ObserverInterface override.
   void ValueChanged(BaseVariable* var);
 
@@ -186,6 +192,9 @@
   // The monotonic clock deadline at which expiration occurs.
   base::Time expiration_monotonic_deadline_;
 
+  // A callback for unregistering the context upon destruction.
+  scoped_ptr<base::Callback<void(EvaluationContext*)>> unregister_cb_;
+
   base::WeakPtrFactory<EvaluationContext> weak_ptr_factory_;
 
   DISALLOW_COPY_AND_ASSIGN(EvaluationContext);
diff --git a/update_manager/evaluation_context_unittest.cc b/update_manager/evaluation_context_unittest.cc
index 9835648..e193718 100644
--- a/update_manager/evaluation_context_unittest.cc
+++ b/update_manager/evaluation_context_unittest.cc
@@ -73,8 +73,9 @@
     fake_clock_.SetMonotonicTime(Time::FromTimeT(1240428300));
     // Mar 2, 2006 1:23:45 UTC.
     fake_clock_.SetWallclockTime(Time::FromTimeT(1141262625));
-    eval_ctx_ = new EvaluationContext(&fake_clock_, default_timeout_,
-                                      default_timeout_);
+    eval_ctx_ = new EvaluationContext(
+        &fake_clock_, default_timeout_, default_timeout_,
+        scoped_ptr<base::Callback<void(EvaluationContext*)>>(nullptr));
   }
 
   virtual void TearDown() {
diff --git a/update_manager/update_manager-inl.h b/update_manager/update_manager-inl.h
index 649dcff..a9f051f 100644
--- a/update_manager/update_manager-inl.h
+++ b/update_manager/update_manager-inl.h
@@ -127,7 +127,16 @@
                                         ExpectedArgs...) const,
     ActualArgs... args) {
   scoped_refptr<EvaluationContext> ec =
-      new EvaluationContext(clock_, evaluation_timeout_, expiration_timeout_);
+      new EvaluationContext(
+          clock_, evaluation_timeout_, expiration_timeout_,
+          scoped_ptr<base::Callback<void(EvaluationContext*)>>(
+              new base::Callback<void(EvaluationContext*)>(
+                  base::Bind(&UpdateManager::UnregisterEvalContext,
+                             weak_ptr_factory_.GetWeakPtr()))));
+  if (!ec_repo_.insert(ec.get()).second) {
+    LOG(ERROR) << "Failed to register evaluation context; this is a bug.";
+  }
+
   // IMPORTANT: To ensure that ActualArgs can be converted to ExpectedArgs, we
   // explicitly instantiate UpdateManager::OnPolicyReadyToEvaluate with the
   // latter in lieu of the former.
diff --git a/update_manager/update_manager.cc b/update_manager/update_manager.cc
index fb3800c..13c208e 100644
--- a/update_manager/update_manager.cc
+++ b/update_manager/update_manager.cc
@@ -14,10 +14,25 @@
                              base::TimeDelta expiration_timeout, State* state)
       : default_policy_(clock), state_(state), clock_(clock),
         evaluation_timeout_(evaluation_timeout),
-        expiration_timeout_(expiration_timeout) {
+        expiration_timeout_(expiration_timeout),
+        weak_ptr_factory_(this) {
   // TODO(deymo): Make it possible to replace this policy with a different
   // implementation with a build-time flag.
   policy_.reset(new ChromeOSPolicy());
 }
 
+UpdateManager::~UpdateManager() {
+  // Remove pending main loop events associated with any of the outstanding
+  // evaluation contexts. This will prevent dangling pending events, causing
+  // these contexts to be destructed once the repo itself is destructed.
+  for (auto& ec : ec_repo_)
+    ec->RemoveObserversAndTimeout();
+}
+
+void UpdateManager::UnregisterEvalContext(EvaluationContext* ec) {
+  if (!ec_repo_.erase(ec)) {
+    LOG(ERROR) << "Unregistering an unknown evaluation context, this is a bug.";
+  }
+}
+
 }  // namespace chromeos_update_manager
diff --git a/update_manager/update_manager.h b/update_manager/update_manager.h
index 2cd21d4..8cfd8f4 100644
--- a/update_manager/update_manager.h
+++ b/update_manager/update_manager.h
@@ -5,6 +5,7 @@
 #ifndef UPDATE_ENGINE_UPDATE_MANAGER_UPDATE_MANAGER_H_
 #define UPDATE_ENGINE_UPDATE_MANAGER_UPDATE_MANAGER_H_
 
+#include <set>
 #include <string>
 
 #include <base/callback.h>
@@ -14,11 +15,21 @@
 
 #include "update_engine/clock_interface.h"
 #include "update_engine/update_manager/default_policy.h"
+#include "update_engine/update_manager/evaluation_context.h"
 #include "update_engine/update_manager/policy.h"
 #include "update_engine/update_manager/state.h"
 
 namespace chromeos_update_manager {
 
+// Comparator for scoped_refptr objects.
+template<typename T>
+struct ScopedRefPtrLess {
+  bool operator()(const scoped_refptr<T>& first,
+                  const scoped_refptr<T>& second) const {
+    return first.get() < second.get();
+  }
+};
+
 // The main Update Manager singleton class.
 class UpdateManager {
  public:
@@ -28,7 +39,7 @@
                 base::TimeDelta evaluation_timeout,
                 base::TimeDelta expiration_timeout, State* state);
 
-  virtual ~UpdateManager() {}
+  virtual ~UpdateManager();
 
   // PolicyRequest() evaluates the given policy with the provided arguments and
   // returns the result. The |policy_method| is the pointer-to-method of the
@@ -111,6 +122,9 @@
                                           Args...) const,
       Args... args);
 
+  // Unregisters (removes from repo) a previously created EvaluationContext.
+  void UnregisterEvalContext(EvaluationContext* ec);
+
   // The policy used by the UpdateManager. Note that since it is a const Policy,
   // policy implementations are not allowed to persist state on this class.
   scoped_ptr<const Policy> policy_;
@@ -131,6 +145,16 @@
   // Timeout for expiration of the evaluation context, used for async requests.
   const base::TimeDelta expiration_timeout_;
 
+  // Repository of previously created EvaluationContext objects. These are being
+  // unregistered (and the reference released) when the context is being
+  // destructed; alternatively, when the UpdateManager instance is destroyed, it
+  // will remove all pending events associated with all outstanding contexts
+  // (which should, in turn, trigger their destruction).
+  std::set<scoped_refptr<EvaluationContext>,
+           ScopedRefPtrLess<EvaluationContext>> ec_repo_;
+
+  base::WeakPtrFactory<UpdateManager> weak_ptr_factory_;
+
   DISALLOW_COPY_AND_ASSIGN(UpdateManager);
 };