We have studied the deformation behavior of the inter-particle regions using a high strength nanostructured alloy (Al84Ni7Gd6Co3) produced by hot pressing of amorphous powders. The inter-particle regions, including soft aluminum and pores, are relatively weak compared to the consolidated particles. Plastic deformation, crack branching and deflection are observed in the inter-particle regions, giving rise to the arrest of cracks. High density of stacking faults and/or nanotwins are formed in the inter-particle regions after plastic deformation. The fracture mode of the Al84Ni7Gd6Co3 nanostructured alloy changes from the inter-particle failure to trans-particle failure with decreasing volume fraction of the inter-particle regions.