The effects of high pressure processing (HPP) on barramundi muscle at 0.1 MPa (control), 150 MPa, 200 MPa, 250 MPa and 300 MPa at 11 ± 2 °C for 3 min were studied before and after immediate blast freezing and storage at −18 °C for up to 18 weeks. Physicochemical measurements including colour, texture profile, drip loss, pH, free fatty acids and thiobarbituric acid (TBA) values were carried out. HPP at 200 MPa significantly increased hardness and delayed lipid oxidation during frozen storage (for up to 18 weeks) without resulting in a cooked appearance of barramundi muscle. However, drip loss of barramundi muscle pressurised at 200 MPa was similar to control samples and during frozen storage. Application of pressures higher than 250 MPa for 3 min resulted in the loss of visual freshness and increased drip loss of barramundi muscle. Thus, application of HPP at an appropriate level (150–200 MPa) before freezing could improve the quality of frozen barramundi muscle.