A hydrogen generator that is able to maintain an ability to supply a reformed gas containing less CO for a long time period while dealing with degradation of a catalytic activity of a shift reaction by a reliable and simple method, an operation method thereof, and a fuel cell system are provided. In a hydrogen generator (50) comprising a reformer (1), a shift converter (6), a water supply device (3A), a material feed device (2A), and a controller (12), the controller (12) is configured to count the number of times of start-up and/or stop of said hydrogen generator (50) and to increase a temperature or a S/C ratio of the reformed gas flowing in said shift converter (6) according to the counted number of times of start-up and/or stop.