diff --git a/policy_manager/evaluation_context.h b/policy_manager/evaluation_context.h
index 3cbd614..ebbaa0f 100644
--- a/policy_manager/evaluation_context.h
+++ b/policy_manager/evaluation_context.h
@@ -7,6 +7,8 @@
 
 #include <map>
 
+#include <base/memory/ref_counted.h>
+
 #include "update_engine/policy_manager/variable.h"
 #include "update_engine/policy_manager/boxed_value.h"
 
@@ -15,7 +17,7 @@
 // The EvaluationContext class is the interface between a policy implementation
 // and the state. The EvaluationContext tracks the variables used by a policy
 // request and caches the returned values, owning those cached values.
-class EvaluationContext {
+class EvaluationContext : public base::RefCounted<EvaluationContext> {
  public:
   EvaluationContext() {}
 
diff --git a/policy_manager/evaluation_context_unittest.cc b/policy_manager/evaluation_context_unittest.cc
index f73171c..6ef6f74 100644
--- a/policy_manager/evaluation_context_unittest.cc
+++ b/policy_manager/evaluation_context_unittest.cc
@@ -21,10 +21,10 @@
 
  protected:
   virtual void SetUp() {
-    eval_ctx_.reset(new EvaluationContext());
+    eval_ctx_ = new EvaluationContext();
   }
 
-  scoped_ptr<EvaluationContext> eval_ctx_;
+  scoped_refptr<EvaluationContext> eval_ctx_;
   FakeVariable<int> fake_int_var_;
 };
 
diff --git a/policy_manager/policy_manager-inl.h b/policy_manager/policy_manager-inl.h
index 798860f..6c361a4 100644
--- a/policy_manager/policy_manager-inl.h
+++ b/policy_manager/policy_manager-inl.h
@@ -5,25 +5,26 @@
 #ifndef CHROMEOS_PLATFORM_UPDATE_ENGINE_POLICY_MANAGER_POLICY_MANAGER_INL_H
 #define CHROMEOS_PLATFORM_UPDATE_ENGINE_POLICY_MANAGER_POLICY_MANAGER_INL_H
 
+#include <base/bind.h>
+
 #include "update_engine/policy_manager/evaluation_context.h"
 
 namespace chromeos_policy_manager {
 
-// Provider of random values.
 template<typename T, typename R, typename... Args>
-EvalStatus PolicyManager::PolicyRequest(T policy_method, R* result,
-                                        Args... args) {
-  EvaluationContext ec;
+EvalStatus PolicyManager::EvaluatePolicy(EvaluationContext* ec,
+                                         T policy_method, R* result,
+                                         Args... args) {
   std::string error;
 
   // First try calling the actual policy.
-  EvalStatus status = (policy_.get()->*policy_method)(&ec, state_.get(), &error,
+  EvalStatus status = (policy_.get()->*policy_method)(ec, state_.get(), &error,
                                                       result, args...);
 
   if (status == EvalStatus::kFailed) {
     LOG(WARNING) << "PolicyRequest() failed with error: " << error;
     error.clear();
-    status = (default_policy_.*policy_method)(&ec, state_.get(), &error,
+    status = (default_policy_.*policy_method)(ec, state_.get(), &error,
                                               result, args...);
 
     if (status == EvalStatus::kFailed) {
@@ -34,6 +35,51 @@
   return status;
 }
 
+
+template<typename T, typename R, typename... Args>
+void PolicyManager::OnPolicyReadyToEvaluate(
+    scoped_refptr<EvaluationContext> ec,
+    base::Callback<void(EvalStatus status, const R& result)> callback,
+    T policy_method, Args... args) {
+  R result;
+  EvalStatus status = EvaluatePolicy(ec, policy_method, &result, args...);
+
+  if (status != EvalStatus::kAskMeAgainLater) {
+    // AsyncPolicyRequest finished.
+    callback.Run(status, result);
+    return;
+  }
+  // Re-schedule the policy request.
+  // TODO(deymo): Use the information gathered on the EvaluationContext to
+  // hook on proper events from changes on the State in order to re-evaluate
+  // the policy after some period of time.
+  base::Closure closure = base::Bind(
+      &PolicyManager::OnPolicyReadyToEvaluate<T, R, Args...>,
+      base::Unretained(this), ec, callback, policy_method, args...);
+  RunFromMainLoopAfterTimeout(closure, base::TimeDelta::FromSeconds(20));
+}
+
+template<typename T, typename R, typename... Args>
+EvalStatus PolicyManager::PolicyRequest(T policy_method, R* result,
+                                        Args... args) {
+  scoped_refptr<EvaluationContext> ec(new EvaluationContext);
+  // A PolicyRequest allways consists on a single evaluation on a new
+  // EvaluationContext.
+  return EvaluatePolicy(ec, policy_method, result, args...);
+}
+
+template<typename T, typename R, typename... Args>
+void PolicyManager::AsyncPolicyRequest(
+    base::Callback<void(EvalStatus, const R& result)> callback,
+    T policy_method, Args... args) {
+
+  scoped_refptr<EvaluationContext> ec = new EvaluationContext;
+  base::Closure closure = base::Bind(
+      &PolicyManager::OnPolicyReadyToEvaluate<T, R, Args...>,
+      base::Unretained(this), ec, callback, policy_method, args...);
+  RunFromMainLoop(closure);
+}
+
 }  // namespace chromeos_policy_manager
 
 #endif  // CHROMEOS_PLATFORM_UPDATE_ENGINE_POLICY_MANAGER_POLICY_MANAGER_INL_H
diff --git a/policy_manager/policy_manager.cc b/policy_manager/policy_manager.cc
index e94df93..146c177 100644
--- a/policy_manager/policy_manager.cc
+++ b/policy_manager/policy_manager.cc
@@ -2,10 +2,13 @@
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
-#include "update_engine/policy_manager/chromeos_policy.h"
 #include "update_engine/policy_manager/policy_manager.h"
+
+#include "update_engine/policy_manager/chromeos_policy.h"
 #include "update_engine/policy_manager/real_state.h"
 
+using base::Closure;
+
 namespace chromeos_policy_manager {
 
 template <typename T>
@@ -24,4 +27,28 @@
   return state_->Init();
 }
 
+void PolicyManager::RunFromMainLoop(const Closure& callback) {
+  Closure* callback_p = new base::Closure(callback);
+  g_idle_add_full(G_PRIORITY_DEFAULT,
+                  OnRanFromMainLoop,
+                  reinterpret_cast<gpointer>(callback_p),
+                  NULL);
+}
+
+void PolicyManager::RunFromMainLoopAfterTimeout(
+    const Closure& callback,
+    base::TimeDelta timeout) {
+  Closure* callback_p = new Closure(callback);
+  g_timeout_add_seconds(timeout.InSeconds(),
+                        OnRanFromMainLoop,
+                        reinterpret_cast<gpointer>(callback_p));
+}
+
+gboolean PolicyManager::OnRanFromMainLoop(gpointer user_data) {
+  Closure* callback_p = reinterpret_cast<Closure*>(user_data);
+  callback_p->Run();
+  delete callback_p;
+  return FALSE;  // Removes the source since a callback can only be called once.
+}
+
 }  // namespace chromeos_policy_manager
diff --git a/policy_manager/policy_manager.h b/policy_manager/policy_manager.h
index b84f493..3966ec5 100644
--- a/policy_manager/policy_manager.h
+++ b/policy_manager/policy_manager.h
@@ -5,6 +5,10 @@
 #ifndef CHROMEOS_PLATFORM_UPDATE_ENGINE_POLICY_MANAGER_POLICY_MANAGER_H
 #define CHROMEOS_PLATFORM_UPDATE_ENGINE_POLICY_MANAGER_POLICY_MANAGER_H
 
+#include <glib.h>
+
+#include <base/callback.h>
+#include <base/memory/ref_counted.h>
 #include <base/memory/scoped_ptr.h>
 
 #include "update_engine/policy_manager/default_policy.h"
@@ -41,11 +45,55 @@
   template<typename T, typename R, typename... Args>
   EvalStatus PolicyRequest(T policy_method, R* result, Args... args);
 
+  // Evaluates the given |policy_method| policy with the provided |args|
+  // arguments and calls the |callback| callback with the result when done.
+  //
+  // If the policy implementation should block, returning a
+  // EvalStatus::kAskMeAgainLater status the policy manager will re-evaluate the
+  // policy until another status is returned.
+  template<typename T, typename R, typename... Args>
+  void AsyncPolicyRequest(
+      base::Callback<void(EvalStatus, const R& result)> callback,
+      T policy_method, Args... args);
+
  private:
   friend class PmPolicyManagerTest;
   FRIEND_TEST(PmPolicyManagerTest, PolicyRequestCallsPolicy);
   FRIEND_TEST(PmPolicyManagerTest, PolicyRequestCallsDefaultOnError);
   FRIEND_TEST(PmPolicyManagerTest, PolicyRequestDoesntBlock);
+  FRIEND_TEST(PmPolicyManagerTest, AsyncPolicyRequestDelaysEvaluation);
+
+  // Schedules the passed |callback| to run from the GLib's main loop after a
+  // timeout if it is given.
+  static void RunFromMainLoop(const base::Closure& callback);
+  static void RunFromMainLoopAfterTimeout(const base::Closure& callback,
+                                          base::TimeDelta timeout);
+
+  // Called by the GLib's main loop when is time to call the callback scheduled
+  // with RunFromMainLopp() and similar functions. The pointer to the callback
+  // passed when scheduling it is passed to this functions as a gpointer on
+  // |user_data|.
+  static gboolean OnRanFromMainLoop(gpointer user_data);
+
+  // EvaluatePolicy() evaluates the passed |policy_method| method on the current
+  // policy with the given |args| arguments. If the method fails, the default
+  // policy is used instead.
+  template<typename T, typename R, typename... Args>
+  EvalStatus EvaluatePolicy(EvaluationContext* ec,
+                            T policy_method, R* result,
+                            Args... args);
+
+  // OnPolicyReadyToEvaluate() is called by the main loop when the evaluation
+  // of the given |policy_method| should be executed. If the evaluation finishes
+  // the |callback| callback is called passing the |result| and the |status|
+  // returned by the policy. If the evaluation returns an
+  // EvalStatus::kAskMeAgainLater state, the |callback| will NOT be called and
+  // the evaluation will be re-scheduled to be called later.
+  template<typename T, typename R, typename... Args>
+  void OnPolicyReadyToEvaluate(
+      scoped_refptr<EvaluationContext> ec,
+      base::Callback<void(EvalStatus status, const R& result)> callback,
+      T policy_method, Args... args);
 
   // The policy used by the PolicyManager. Note that since it is a const Policy,
   // policy implementations are not allowed to persist state on this class.
diff --git a/policy_manager/policy_manager_unittest.cc b/policy_manager/policy_manager_unittest.cc
index b9253d3..9e28ebc 100644
--- a/policy_manager/policy_manager_unittest.cc
+++ b/policy_manager/policy_manager_unittest.cc
@@ -2,19 +2,28 @@
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
+#include <algorithm>
+#include <string>
+#include <vector>
+
+#include <base/bind.h>
 #include <base/memory/scoped_ptr.h>
 #include <base/time.h>
 #include <gtest/gtest.h>
 #include <gmock/gmock.h>
-#include <string>
 
 #include "update_engine/policy_manager/default_policy.h"
 #include "update_engine/policy_manager/mock_policy.h"
 #include "update_engine/policy_manager/pmtest_utils.h"
 #include "update_engine/policy_manager/policy_manager.h"
+#include "update_engine/test_utils.h"
 
+using base::Bind;
+using base::Callback;
 using base::TimeDelta;
+using std::pair;
 using std::string;
+using std::vector;
 
 using testing::_;
 using testing::Return;
@@ -43,7 +52,7 @@
   }
 };
 
-// The LazyPolicy always returns
+// The LazyPolicy always returns EvalStatus::kAskMeAgainLater.
 class LazyPolicy : public DefaultPolicy {
   virtual EvalStatus UpdateCheckAllowed(EvaluationContext* ec, State* state,
                                         string* error,
@@ -52,6 +61,16 @@
   }
 };
 
+// AccumulateCallsCallback() adds to the passed |acc| accumulator vector pairs
+// of EvalStatus and T instances. This allows to create a callback that keeps
+// track of when it is called and the arguments passed to it, to be used with
+// the PolicyManager::AsyncPolicyRequest().
+template<typename T>
+static void AccumulateCallsCallback(vector<pair<EvalStatus, T>>* acc,
+                                    EvalStatus status, const T& result) {
+  acc->push_back(std::make_pair(status, result));
+}
+
 TEST_F(PmPolicyManagerTest, PolicyRequestCall) {
   bool result;
   EvalStatus status = pmut_.PolicyRequest(&Policy::UpdateCheckAllowed, &result);
@@ -89,4 +108,22 @@
   EXPECT_EQ(status, EvalStatus::kAskMeAgainLater);
 }
 
+TEST_F(PmPolicyManagerTest, AsyncPolicyRequestDelaysEvaluation) {
+  // To avoid differences in code execution order between an AsyncPolicyRequest
+  // call on a policy that returns AskMeAgainLater the first time and one that
+  // succeeds the first time, we ensure that the passed callback is called from
+  // the main loop in both cases even when we could evaluate it right now.
+  pmut_.policy_.reset(new FailingPolicy());
+
+  vector<pair<EvalStatus, bool>> calls;
+  Callback<void(EvalStatus, const bool& result)> callback =
+      Bind(AccumulateCallsCallback<bool>, &calls);
+
+  pmut_.AsyncPolicyRequest(callback, &Policy::UpdateCheckAllowed);
+  // The callback should wait until we run the main loop for it to be executed.
+  EXPECT_EQ(0, calls.size());
+  chromeos_update_engine::RunGMainLoopMaxIterations(100);
+  EXPECT_EQ(1, calls.size());
+}
+
 }  // namespace chromeos_policy_manager
diff --git a/test_utils.cc b/test_utils.cc
index e73146c..e46b399 100644
--- a/test_utils.cc
+++ b/test_utils.cc
@@ -310,4 +310,13 @@
   unmounter_.reset(new ScopedFilesystemUnmounter(*mnt_path));
 }
 
+int RunGMainLoopMaxIterations(int iterations) {
+  int result;
+  GMainContext* context = g_main_context_default();
+  for (result = 0;
+       result < iterations && g_main_context_iteration(context, FALSE);
+       result++) {}
+  return result;
+}
+
 }  // namespace chromeos_update_engine
diff --git a/test_utils.h b/test_utils.h
index 2b72af1..008e1c5 100644
--- a/test_utils.h
+++ b/test_utils.h
@@ -273,6 +273,14 @@
   scoped_ptr<ScopedFilesystemUnmounter> unmounter_;
 };
 
+// Runs the default GLib main loop at most |iterations| times. This
+// dispatches all the events that are already waiting in the main loop and
+// those that get scheduled as a result of these events being attended.
+// Returns the number of iterations the main loop was ran. If there are more
+// than |iterations| events to attend, then this function returns |iterations|
+// and the remaining events are not dispatched.
+int RunGMainLoopMaxIterations(int iterations);
+
 }  // namespace chromeos_update_engine
 
 #endif  // CHROMEOS_PLATFORM_UPDATE_ENGINE_TEST_UTILS_H__