A storage device including: a nonvolatile memory which includes a first memory block configured to store a first user data; and a controller configured to perform a patrol read on the first user data, wherein the controller is configured to increase a reclaim count for the first user data, when the first user data requires a reclaim, the controller is configured to determine that the first user data is a cold data, when the reclaim count for the first user data is greater than a reclaim threshold value, the controller is configured to perform a first reclaim on the first user data when the first user data is determined to be the cold data, and the nonvolatile memory is configured to store the first user data in a second memory block different from the first memory block in response to the first reclaim.