A method and apparatus for compressing relative addresses and for storage of compressed relative addresses. A relative virtual address is computed in a particular stage of a processor pipeline and then compressed according to one or more compression techniques for storage in a micro-operation storage. A compressed relative address is retrieved from one or more micro-operation entries of the micro-operation storage and an uncompressed virtual address is reconstructed from the compressed relative address and an instruction pointer (IP) address associated with the head of the micro-operation storage line in which the compressed relative address was stored. IP-relative addresses may be computed in a manner similar to relative branch targets, then compressed and stored in one or more micro-operation entries of a micro-operation storage line to be reconstructed later according to an IP address associated with the respective micro-operation storage line in which their compressed counterpart was stored.