In modern embedded systems, the trust in comprehensive security standards all along the product life cycle has become an increasingly important access-to-market requirement. However, these security standards rely on mandatory immunity assumptions such as the integrity and authenticity of an initial system configuration typically loaded from Non-Volatile Memory (NVM). This applies especially to FPGA-based Programmable System-on-Chip (PSoC) architectures, since object codes as well as configuration data easily exceed the capacity of a secure bootROM. In this context, an attacker could try to alter the content of the NVM device in order to manipulate the system. The PSoC therefore relies on the integrity of the NVM particularly at boot-time. In this paper, we propose a methodology for securely booting from an NVM in a potentially unsecure environment by exploiting the reconfigurable logic of the FPGA. Here, the FPGA serves as a secure anchor point by performing required integrity and authenticity verifications prior to the configuration and execution of any user application loaded from the NVM on the PSoC. The proposed secure boot process is based on the following assumptions and steps: 1) The boot configurationis stored on a fully encrypted Secure Digital memory card (SD card) or alternatively Flash acting as NVM. 2) At boot time, a hardware design called Trusted Memory-Interface Unit (TMIU) is loaded to verify first the authenticity of the deployed NVM and then after decryption the integrity of its content. To demonstrate the practicability of our approach, we integrated the methodology into the vendor-specific secure boot process of a Xilinx Zynq PSoC and evaluated the design objectives performance, power and resource costs.