Australian rock lobster (Jasus edwardsii) liver contains approximately 24.3% (w/w) lipids, which can contain a high amount of polyunsaturated fatty acids (PUFAs). However, this material has been found to be contaminated with arsenic (240 mg/kg) and cadmium (8 mg/kg). The high level of contaminants in the raw material and the large amount of PUFAs in the lipids prove a significant challenge in the extraction of high-quality lipids from this byproduct by conventional methods. Supercritical carbon dioxide (SC-CO2) extraction is a highly promising technology for lipid extraction with advantages including low contamination and low oxidation. The technique was optimized to achieve nearly 94% extraction of lipids relative to conventional Soxhlet extraction in Australian rock lobster liver at conditions of 35 MPa and 50 °C for 4 h. The extracted lipids are significantly enriched in PUFAs at 31.3% of total lipids, 4 times higher than those in the lipids recovered by Soxhlet extraction (7.8%). Specifically, the concentrations of docosahexaenoic acid (DHA) and eicosapentaenoic acid (EPA) in SC-CO2 extraction are 7 times higher than those obtained by Soxhlet extraction. Moreover, very small amounts of toxic heavy metals such as lead (Pb), arsenic (As), mercury (Hg), and cadmium (Cd) were detected in the SC-CO2-extracted lipids, 0.5-27 times lower than those in the Soxhlet-extracted lipids, which are 40-200 times lower than the regulatory limit maximum values. The low levels of contaminants and the high proportion of PUFAs (dominated by DHA and EPA) found in the SC-CO2-extracted lipids from Australian rock lobster liver suggest that the material could potentially be used as a valuable source of essential fatty acids for human consumption.