We tackle the problem of fault-free assumptions in current PLB and interconnect built-in-self-test (BIST) techniques for FPGAs. These assumptions were made in order to develop strong BISTmethods for one class of components (PLBs or interconnects) while assuming that the other class is fault-free. This results in a cyclical conundrum that renders current PLB and interconnect BIST techniques impractical, since current deepsubmicron FPGAs as well as those of emerging single-digit nanometer technologies are expected to have a profusion of hard (permanent) PLB as well as interconnect faults. We address this issue here and develop a novel method M-BIST that uses a combination of (i) iterative bootstrapping that without any knowledge of the state of any PLB or interconnect determines a minimum contingent of fault-free test circuit components with high probability, and (ii) mixed testing of PLBs and interconnects in an interleaved manner that identifies fault-free components that are used in subsequent testing phases until the entire FPGA is tested. This approach is overlaid on current state-of-the-art PLB and interconnect BIST techniques. Simulation results obtained for faults present in both PLBs and interconnects show significant improvements in both fault coverage and false positives yielded by M-BIST compared to the PLB-only and interconnect-only BIST techniques used within the M-BIST wrapper that make fault-free assumptions about the other component type.