Relocation of instructions that use relative addressing. Metadata relating to an instruction that uses relative addressing to access data and is to be relocated is stored prior to relocation. Based on relocating the instruction from one memory location to another memory location, a determination is made of an address to be used to access the data by the instruction. The determining is based on at least one of the metadata or an address of the another memory location. The instruction is executed at the another memory location, and the determined address is used to access the data.