Disclosed are an autonomously traveling mobile robot and a traveling control method thereof, which can control the traveling of the mobile robot according to a first traveling mode in which the mobile robot travels by following obstacles located around the mobile robot or a second traveling mode in which the mobile robot travels in consideration of a positional relation with an existing traveling trajectory through which the mobile robot has already traveled, and generate candidate spots where the mobile robot can travel while the mobile robot travels along the traveling trajectory to implement a spiral cleaning pattern.