diff --git a/src/device.c b/src/device.c
index 9dd657c..96e798f 100644
--- a/src/device.c
+++ b/src/device.c
@@ -993,7 +993,6 @@ static void device_remove_stored(struct btd_device *device)
 		delete_entry(&src, "aliases", addr);
 		device_set_bonded(device, FALSE);
 		device_set_paired(device, FALSE);
-		btd_adapter_remove_bonding(device->adapter, &device->bdaddr);
 	}
 	delete_entry(&src, "profiles", addr);
 	delete_entry(&src, "trusts", addr);
@@ -2038,6 +2037,9 @@ void device_set_paired(struct btd_device *device, gboolean value)
 	if (device->paired == value)
 		return;
 
+	if (!value)
+		btd_adapter_remove_bonding(device->adapter, &device->bdaddr);
+
 	device->paired = value;
 
 	emit_property_changed(conn, device->path, DEVICE_INTERFACE, "Paired",