The fortification problem (FP) is commonly formulated as a defender-attacker-defender (DAD) model. In this setting, a planner first hardens up to h components, then an attacker interdicts up to k components, and finally the defender solves a recourse problem to maintain system operations. A key limitation of the DAD model is the assumption that the planner has full knowledge of the attacker’s capability and the operating condition of the system. To address these sources of uncertainty, we formulate the fortification problem under scenario uncertainty (FP-SU). Existing methods, such as column-and-constraint generation (CCG) algorithms, struggle to scale efficiently as the number of scenarios increases. We propose the Historically-Observed Precedent Sampling (HOPS) algorithm that exploits the scenario structure to generate valid lower bounds and implicitly enumerate candidate defenses. We prove that the HOPS algorithm converges in finitely many iterations to an optimal solution. Computational experiments on benchmark electrical power grid test cases demonstrate substantial improvements in scalability and runtime relative to existing methods.