Persistent halogenated compounds (PHC) are of concern for human and environmental health. Persistent Organic Pollutants (POPs) are regulated by international treaties, but alternative compounds such as novel brominated flame retardants (NBFRs) and Dechlorane Plus (DP) are not—yet they are increasingly used. There are no data on PHCs in coral reef biota from tropical islands in the western Indian Ocean (WIO). For this assessment, three hard coral genera, two soft coral genera, and ember parrotfish (Scarus rubroviolaceus) were collected from the remote Rodrigues, Agalega, and St. Brandon’s Atoll (Republic of Mauritius) in the Mascarene Basin of the WIO. Five compounds — Pentabromotoluene (PBT), γ-HCH, p,p’-DDE, HCB, and BDE-47— were quantifiable in all samples. Hard coral consistently contained the lowest concentrations of PHCs, except for NBFRs. The presence of BDE-47 suggests long-range aerial transport. We quantified DP, currently a candidate POP, in coral reef biota. PBT was measured in all samples also suggests long-range transport. Because the hard coral, soft coral, and fish had differing concentrations and patterns of PHCs, future surveys should stratify sampling accordingly. Agalega and St. Brandon’s Atoll can be considered as locations to monitor changes in background concentrations of pollutants due to their remoteness.