A method and apparatus predicting the outcome of a conditional branch instruction based on the previous performance of the branch, rather than on the instruction fields. The prediction of the outcome of a conditional branch instruction is performed utilizing a table that records the history of the outcome of the branch at a given memory location. A decode-time history table (DHT) is utilized. The DHT attempts to guess only the outcome of a conditional branch instruction, but not its target address. Thus, it can only be used to guess the branch outcomes at decode time when the target address is available. During the decoding of a conditional branch instruction, a table is accessed using the memory address of the branch instruction itself or some portions thereof. The table records the history of the outcomes of the branch at this memory location up to the congruence of the table size. A combinational circuit determines the guess (taken or not taken) from the branch history as provided by the table.