Recent screening surveys have shown the presence of unknown halogenated compounds in the marine environment at comparable levels to persistent organic pollutants (POPs). However, their exposure levels and profiles in marine organisms and bioaccumulative potentials remain unclear. The present study performed nontarget/target screening of organohalogen compounds (OHCs) in mussel and sediment samples collected from Hiroshima Bay, Japan, in 2012 and 2018 by using integrated analyses of two-dimensional gas chromatography–high resolution time-of-flight mass spectrometry (GC×GC–HRToFMS) and magnetic sector GC–HRMS. Nontarget analysis by GC×GC–HRToFMS revealed the detection of approximately 60 OHCs including unknown mixed halogenated compounds (UHC-Br3–5Cl) with molecular formulae of C9H6Br3ClO, C9H5Br4ClO, and C9H4Br5ClO in the mussel. Interestingly, UHC-Br3–5Cl concentrations in the mussel samples, which were semi-quantified by GC–HRMS, were comparable to or higher than those of POPs at all the locations surveyed, and their geographical distribution patterns differed from those of other OHCs. These results suggest that UHC-Br3–5Cl are ubiquitous in coastal waters of Hiroshima Bay and derived from a specific source(s). The biota-sediment accumulation factors (BSAFs) of UHC-Br3–5Cl, estimated for a paired sample set of mussel (ng/g lw) and sediment (ng/g TOC), were 1 order of magnitude higher than those for POPs with similar log K ow values, indicating their high bioaccumulative potential.