diff --git a/src/device.c b/src/device.c
index f59b6c1..df440ce 100644
--- a/src/device.c
+++ b/src/device.c
@@ -6028,6 +6028,14 @@ void device_bonding_complete(struct btd_device *device, uint8_t bdaddr_type,
 
 	if (status) {
 		device_cancel_authentication(device, TRUE);
+
+		/* Put the device back to the temporary state so that it will be
+		 * treated as a newly discovered device.
+		 */
+		if (!device_is_paired(device, bdaddr_type) &&
+				!device_is_trusted(device))
+			btd_device_set_temporary(device, true);
+
 		device_bonding_failed(device, status);
 		return;
 	}