The present invention provides a construction machine where overheating of mounted electric devices can be prevented properly with a simple structure and a method of controlling the construction machine. For this purpose, a pump target discharge flow rate of a hydraulic pump is calculated based on an operated amount of an operating unit, a temperature of an electric device mounted on the construction machine is detected, an engine minimum speed, which is a minimum possible speed of an engine in carrying out low-speed matching for matching output of the engine and pump absorbing horsepower of the hydraulic pump to each other in a low-speed region where speed of the engine is lower than set speed, is calculated by using the detected temperature of the electric device, and a maximum value out of a corresponding speed of the pump target discharge flow rate and the engine minimum speed is generated as a candidate for an engine target speed.