A processor using a branch instruction execution cache and a method of operating the same are disclosed. The processor according to an example embodiment of the present invention includes a fetch unit, a branch prediction unit, an instruction queue, a decoding unit and an execution unit operating in a pipeline manner, and includes a branch instruction execution cache that stores address and decode information of a transferred instruction output from the decoding unit, and provides the stored address and at least some of pieces of the decode information to the execution unit in order to overcome branch misprediction when the execution unit determines the branch misprediction. Therefore, with the processor according to an example embodiment of the present invention, overhead of pipeline initialization can be minimized to prevent performance degradation of the processor and reduce power consumption of the processor.