Halogenated polycyclic aromatic hydrocarbon (HPAH) concentrations in tissues from three tuna species Thunnus albacares (yellowfin tuna), Katsuwonus pelamis (skipjack tuna), and Auxis thazard (frigate tuna) were determined by high-resolution gas chromatography Orbitrap mass spectrometry. The tuna samples were collected from the Indian Ocean. The instrument conditions gave high mass accuracy at 0.9 m/z isolation width of the mass filter and a mass error of <±1.0 ppm for many HPAHs. A total of 29 of the 30 targets chlorinated PAHs (ClPAHs) and 20 of the 21 targets brominated PAHs (BrPAHs) were detected in the tuna muscle samples. The mean total ClPAH, BrPAH and PAH concentrations for tuna were 127.2, 156.6 and 682.8 ng/g lipid weight, respectively. The mean total ClPAH and BrPAH concentrations (ng/g lipid weight) in the tuna were considerably lower than that of PAH concentrations. The mean total ClPAH, BrPAH and PAH concentrations in T. albacares respectively were 185.8, 249.2 and 784.1 ng/g lipid weight, irrespective of the body sizes. The mean total ClPAH, BrPAH and PAH concentrations in K. pelamis respectively were 45.1, 24.8 and 555.6 ng/g lipid weight. The mean total ClPAH, BrPAH and PAH concentrations in A. thazard respectively were 34.09, 4.73 and 433.24 ng/g lipid weight. The total ClPAH concentrations and body weights significantly positively correlated for T. albacares. The mean total ClPAH concentration in white muscles was significantly higher (p < 0.05) for large than for small T. albacares. This suggests ClPAHs could bioaccumulate in T. albacares, possibly because they are poorly metabolized. The chlorinated phenanthrene and pyrene concentrations indicated tuna accumulate these compounds increasingly effectively as the tuna grow. This was the first time large numbers of HPAHs were found in biological samples. HPAHs may adversely affect the health of humans consuming tuna.