diff --git a/libweave/examples/ubuntu/main.cc b/libweave/examples/ubuntu/main.cc
index b9f0806..5a7c2fa 100644
--- a/libweave/examples/ubuntu/main.cc
+++ b/libweave/examples/ubuntu/main.cc
@@ -219,6 +219,14 @@
   base::WeakPtrFactory<CommandHandler> weak_ptr_factory_{this};
 };
 
+void RegisterDeviceSuccess(weave::Device* device) {
+  LOG(INFO) << "Device registered: " << device->GetSettings().cloud_id;
+}
+
+void RegisterDeviceError(const weave::Error* error) {
+  LOG(ERROR) << "Fail to register device: " << error->GetMessage();
+}
+
 }  // namespace
 
 int main(int argc, char** argv) {
@@ -262,13 +270,9 @@
       &bluetooth);
 
   if (!registration_ticket.empty()) {
-    weave::ErrorPtr error;
-    auto device_id = device->Register(registration_ticket, &error);
-    if (error != nullptr) {
-      LOG(ERROR) << "Fail to register device: " << error->GetMessage();
-    } else {
-      LOG(INFO) << "Device registered: " << device_id;
-    }
+    device->Register(registration_ticket,
+                     base::Bind(&RegisterDeviceSuccess, device.get()),
+                     base::Bind(&RegisterDeviceError));
   }
 
   CommandHandler handler(device.get(), &task_runner);
diff --git a/libweave/include/weave/device.h b/libweave/include/weave/device.h
index 7e49202..7fbe248 100644
--- a/libweave/include/weave/device.h
+++ b/libweave/include/weave/device.h
@@ -118,10 +118,11 @@
   virtual void AddGcdStateChangedCallback(
       const GcdStateChangedCallback& callback) = 0;
 
-  // Registers the device. Returns a device ID on success.
+  // Registers the device.
   // This is testing method and should not be used by applications.
-  virtual std::string Register(const std::string& ticket_id,
-                               ErrorPtr* error) = 0;
+  virtual void Register(const std::string& ticket_id,
+                        const SuccessCallback& success_callback,
+                        const ErrorCallback& error_callback) = 0;
 
   // Handler should display pin code to the user.
   using PairingBeginCallback =
diff --git a/libweave/include/weave/test/mock_device.h b/libweave/include/weave/test/mock_device.h
index 310d5b4..0d8a6da 100644
--- a/libweave/include/weave/test/mock_device.h
+++ b/libweave/include/weave/test/mock_device.h
@@ -44,8 +44,10 @@
   MOCK_CONST_METHOD0(GetGcdState, GcdState());
   MOCK_METHOD1(AddGcdStateChangedCallback,
                void(const GcdStateChangedCallback& callback));
-  MOCK_METHOD2(Register,
-               std::string(const std::string& ticket_id, ErrorPtr* error));
+  MOCK_METHOD3(Register,
+               void(const std::string& ticket_id,
+                    const SuccessCallback& success_callback,
+                    const ErrorCallback& error_callback));
   MOCK_METHOD2(AddPairingChangedCallbacks,
                void(const PairingBeginCallback& begin_callback,
                     const PairingEndCallback& end_callback));
diff --git a/libweave/src/device_manager.cc b/libweave/src/device_manager.cc
index 86c9150..9105352 100644
--- a/libweave/src/device_manager.cc
+++ b/libweave/src/device_manager.cc
@@ -151,9 +151,10 @@
   return state_manager_->GetState();
 }
 
-std::string DeviceManager::Register(const std::string& ticket_id,
-                                    ErrorPtr* error) {
-  return device_info_->RegisterDevice(ticket_id, error);
+void DeviceManager::Register(const std::string& ticket_id,
+                             const SuccessCallback& success_callback,
+                             const ErrorCallback& error_callback) {
+  device_info_->RegisterDevice(ticket_id, success_callback, error_callback);
 }
 
 void DeviceManager::AddPairingChangedCallbacks(
diff --git a/libweave/src/device_manager.h b/libweave/src/device_manager.h
index 8c85a1b..16e0601 100644
--- a/libweave/src/device_manager.h
+++ b/libweave/src/device_manager.h
@@ -58,7 +58,9 @@
                         const base::Value& value,
                         ErrorPtr* error) override;
   std::unique_ptr<base::DictionaryValue> GetState() const override;
-  std::string Register(const std::string& ticket_id, ErrorPtr* error) override;
+  void Register(const std::string& ticket_id,
+                const SuccessCallback& success_callback,
+                const ErrorCallback& error_callback) override;
   GcdState GetGcdState() const override;
   void AddGcdStateChangedCallback(
       const GcdStateChangedCallback& callback) override;
diff --git a/libweave/src/device_registration_info.cc b/libweave/src/device_registration_info.cc
index e712130..adb1994 100644
--- a/libweave/src/device_registration_info.cc
+++ b/libweave/src/device_registration_info.cc
@@ -525,12 +525,22 @@
                  error_callback);
 }
 
-std::string DeviceRegistrationInfo::RegisterDevice(const std::string& ticket_id,
-                                                   ErrorPtr* error) {
+void DeviceRegistrationInfo::RegisterDevice(
+    const std::string& ticket_id,
+    const SuccessCallback& success_callback,
+    const ErrorCallback& error_callback) {
+  ErrorPtr error;
+
+  auto on_error = [this, &error_callback](ErrorPtr error) {
+    task_runner_->PostDelayedTask(
+        FROM_HERE, base::Bind(error_callback, base::Owned(error.release())),
+        {});
+  };
+
   std::unique_ptr<base::DictionaryValue> device_draft =
-      BuildDeviceResource(error);
+      BuildDeviceResource(&error);
   if (!device_draft)
-    return std::string();
+    return on_error(std::move(error));
 
   base::DictionaryValue req_json;
   req_json.SetString("id", ticket_id);
@@ -542,29 +552,29 @@
 
   RequestSender sender{http::kPatch, url, http_client_};
   sender.SetJsonData(req_json);
-  auto response = sender.SendAndBlock(error);
+  auto response = sender.SendAndBlock(&error);
 
   if (!response)
-    return std::string();
-  auto json_resp = ParseJsonResponse(*response, error);
+    return on_error(std::move(error));
+  auto json_resp = ParseJsonResponse(*response, &error);
   if (!json_resp)
-    return std::string();
+    return on_error(std::move(error));
   if (!IsSuccessful(*response)) {
-    ParseGCDError(json_resp.get(), error);
-    return std::string();
+    ParseGCDError(json_resp.get(), &error);
+    return on_error(std::move(error));
   }
 
   url = GetServiceURL("registrationTickets/" + ticket_id + "/finalize",
                       {{"key", GetSettings().api_key}});
-  response = RequestSender{http::kPost, url, http_client_}.SendAndBlock(error);
+  response = RequestSender{http::kPost, url, http_client_}.SendAndBlock(&error);
   if (!response)
-    return std::string();
-  json_resp = ParseJsonResponse(*response, error);
+    return on_error(std::move(error));
+  json_resp = ParseJsonResponse(*response, &error);
   if (!json_resp)
-    return std::string();
+    return on_error(std::move(error));
   if (!IsSuccessful(*response)) {
-    ParseGCDError(json_resp.get(), error);
-    return std::string();
+    ParseGCDError(json_resp.get(), &error);
+    return on_error(std::move(error));
   }
 
   std::string auth_code;
@@ -575,9 +585,9 @@
       !json_resp->GetString("robotAccountAuthorizationCode", &auth_code) ||
       !json_resp->GetDictionary("deviceDraft", &device_draft_response) ||
       !device_draft_response->GetString("id", &cloud_id)) {
-    Error::AddTo(error, FROM_HERE, kErrorDomainGCD, "unexpected_response",
+    Error::AddTo(&error, FROM_HERE, kErrorDomainGCD, "unexpected_response",
                  "Device account missing in response");
-    return std::string();
+    return on_error(std::move(error));
   }
 
   UpdateDeviceInfoTimestamp(*device_draft_response);
@@ -591,21 +601,21 @@
        {"redirect_uri", "oob"},
        {"scope", "https://www.googleapis.com/auth/clouddevices"},
        {"grant_type", "authorization_code"}});
-  response = sender2.SendAndBlock(error);
+  response = sender2.SendAndBlock(&error);
 
   if (!response)
-    return std::string();
+    return on_error(std::move(error));
 
-  json_resp = ParseOAuthResponse(*response, error);
+  json_resp = ParseOAuthResponse(*response, &error);
   int expires_in = 0;
   std::string refresh_token;
   if (!json_resp || !json_resp->GetString("access_token", &access_token_) ||
       !json_resp->GetString("refresh_token", &refresh_token) ||
       !json_resp->GetInteger("expires_in", &expires_in) ||
       access_token_.empty() || refresh_token.empty() || expires_in <= 0) {
-    Error::AddTo(error, FROM_HERE, kErrorDomainGCD, "unexpected_response",
+    Error::AddTo(&error, FROM_HERE, kErrorDomainGCD, "unexpected_response",
                  "Device access_token missing in response");
-    return std::string();
+    return on_error(std::move(error));
   }
 
   access_token_expiration_ =
@@ -617,12 +627,13 @@
   change.set_refresh_token(refresh_token);
   change.Commit();
 
+  task_runner_->PostDelayedTask(FROM_HERE, success_callback, {});
+
   StartNotificationChannel();
 
   // We're going to respond with our success immediately and we'll connect to
   // cloud shortly after.
-  ScheduleCloudConnection(base::TimeDelta::FromSeconds(0));
-  return cloud_id;
+  ScheduleCloudConnection({});
 }
 
 void DeviceRegistrationInfo::DoCloudRequest(
diff --git a/libweave/src/device_registration_info.h b/libweave/src/device_registration_info.h
index c797102..3a57982 100644
--- a/libweave/src/device_registration_info.h
+++ b/libweave/src/device_registration_info.h
@@ -64,7 +64,9 @@
 
   void AddGcdStateChangedCallback(
       const Device::GcdStateChangedCallback& callback);
-  std::string RegisterDevice(const std::string& ticket_id, ErrorPtr* error);
+  void RegisterDevice(const std::string& ticket_id,
+                      const SuccessCallback& success_callback,
+                      const ErrorCallback& error_callback);
 
   void UpdateDeviceInfo(const std::string& name,
                         const std::string& description,
diff --git a/libweave/src/device_registration_info_unittest.cc b/libweave/src/device_registration_info_unittest.cc
index cfd5b86..5245458 100644
--- a/libweave/src/device_registration_info_unittest.cc
+++ b/libweave/src/device_registration_info_unittest.cc
@@ -482,17 +482,23 @@
         return ReplyWithJson(200, json);
       })));
 
-  std::string cloud_id =
-      dev_reg_->RegisterDevice(test_data::kClaimTicketId, nullptr);
+  bool done = false;
+  dev_reg_->RegisterDevice(
+      test_data::kClaimTicketId, base::Bind([this, &done]() {
+        done = true;
+        task_runner_.Break();
+        EXPECT_EQ(GcdState::kConnecting, GetGcdState());
 
-  EXPECT_EQ(test_data::kDeviceId, cloud_id);
-  EXPECT_EQ(GcdState::kConnecting, GetGcdState());
-
-  // Validate the device info saved to storage...
-  EXPECT_EQ(test_data::kDeviceId, dev_reg_->GetSettings().cloud_id);
-  EXPECT_EQ(test_data::kRefreshToken, dev_reg_->GetSettings().refresh_token);
-  EXPECT_EQ(test_data::kRobotAccountEmail,
-            dev_reg_->GetSettings().robot_account);
+        // Validate the device info saved to storage...
+        EXPECT_EQ(test_data::kDeviceId, dev_reg_->GetSettings().cloud_id);
+        EXPECT_EQ(test_data::kRefreshToken,
+                  dev_reg_->GetSettings().refresh_token);
+        EXPECT_EQ(test_data::kRobotAccountEmail,
+                  dev_reg_->GetSettings().robot_account);
+      }),
+      base::Bind([](const Error* error) { ADD_FAILURE(); }));
+  task_runner_.Run();
+  EXPECT_TRUE(done);
 }
 
 TEST_F(DeviceRegistrationInfoTest, OOBRegistrationStatus) {
diff --git a/libweave/src/privet/cloud_delegate.cc b/libweave/src/privet/cloud_delegate.cc
index 045a235..83cb6fb 100644
--- a/libweave/src/privet/cloud_delegate.cc
+++ b/libweave/src/privet/cloud_delegate.cc
@@ -284,12 +284,21 @@
       return;
     }
 
-    if (!device_->RegisterDevice(ticket_id, &error).empty()) {
-      backoff_entry_.InformOfRequest(true);
-      setup_state_ = SetupState(SetupState::kSuccess);
-      return;
-    }
+    device_->RegisterDevice(
+        ticket_id, base::Bind(&CloudDelegateImpl::RegisterDeviceSuccess,
+                              setup_weak_factory_.GetWeakPtr()),
+        base::Bind(&CloudDelegateImpl::RegisterDeviceError,
+                   setup_weak_factory_.GetWeakPtr(), ticket_id, deadline));
+  }
 
+  void RegisterDeviceSuccess() {
+    backoff_entry_.InformOfRequest(true);
+    setup_state_ = SetupState(SetupState::kSuccess);
+  }
+
+  void RegisterDeviceError(const std::string& ticket_id,
+                           const base::Time& deadline,
+                           const Error* error) {
     // Registration failed. Retry with backoff.
     backoff_entry_.InformOfRequest(false);
     task_runner_->PostDelayedTask(
diff --git a/libweave/src/weave_unittest.cc b/libweave/src/weave_unittest.cc
index 3b68e3e..69250fd 100644
--- a/libweave/src/weave_unittest.cc
+++ b/libweave/src/weave_unittest.cc
@@ -329,7 +329,15 @@
 
   InitDnsSdPublishing(true, "DB");
 
-  EXPECT_EQ("CLOUD_ID", device_->Register("TICKET_ID", nullptr));
+  bool done = false;
+  device_->Register("TICKET_ID", base::Bind([this, &done]() {
+                      done = true;
+                      task_runner_.Break();
+                      EXPECT_EQ("CLOUD_ID", device_->GetSettings().cloud_id);
+                    }),
+                    base::Bind([](const Error* error) { ADD_FAILURE(); }));
+  task_runner_.Run();
+  EXPECT_TRUE(done);
 }
 
 class WeaveWiFiSetupTest : public WeaveTest {