An apparatus comprises a branch predictor to predict an outcome of a branch instruction to be processed by processing circuitry, based on branch prediction state information stored in one or more branch prediction structures, and a call path tracking element to store call path tracking information, where in response to a procedure calling instruction processed by the processing circuitry, the call path tracking information is updated depending on at least a portion of an address associated with the procedure calling instruction. The one or more branch prediction structures include at least one call-path-indexed branch prediction structure which is indexed based on an index value which depends on a portion of the call path tracking information stored in the call path tracking element.