As computer software grow larger in size and complexity, there is an ever increasing concern over security. In an age where software controls almost everything, from the cars we drive to the airplanes we fly in, this concern is valid now more than ever. Attackers are evolving new ways to exploit vulnerabilities in software everyday, while the computer security community struggles to keep up. One of the most prominent of these attack methods is code reuse attacks - specifically return-oriented programming and its variants. Traditionally, defense techniques have mostly either been at the hardware level or in the software layer. While these defenses have their own strengths and weaknesses, a layer of abstraction that has mostly been unexplored is the architecture. Computer architecture lies at the boundary of hardware and software, where we can harness the strengths of both layers. This work explores the potential security benefit that we can extract from decoupling the architectural state that the system presents to the software, from the micro-architectural state it maintains in hardware. Recent research has shown the potential for heterogeneous-ISA chip multiprocessors to provide both performance and energy benefits. We propose Heterogeneous-ISA Program State Relocation, an architecture based on heterogeneous-ISA computing that randomizes the ISA a program executes on, and couple that with a defense mechanism that dynamically randomizes the program state. We describe the proposed architecture, our implementation of it, and perform a thorough evaluation of its potential as an effective defense technique