While previous studies have found that unknown natural and synthetic organo-bromine compounds (NSOBCs) contributed more than 99% of the total organic bromine (Br) in the environment, there was no efficient method for untargeted screening to identify NSOBCs in environmental samples. A novel, untargeted method for identifying, based on ultra-high resolution mass spectrometry (UHRMS) with the Q Exactive instrument was developed. This method included a novel data-independent precursor isolation and characteristic fragment (DIPIC-Frag) procedure to identify NSOBCs. One hundred and eighty successive 5-m/z-wide windows were used to isolate precursor ions. This resulted in sufficient dynamic range and specificity to identify peaks of Br fragment ion for analysis. A total of 2520 peaks of NSOBC compounds containing Br were observed in sediments from Lake Michigan, USA. A new chemometric strategy which combined chromatographic profiles, isotope peaks, precursor isolation window information and intensities was used to identify precursor ions and chemical formulae for detected brominated compounds. Precursor ions for 2163 of the 2520 NSOBCs peaks (86%) were identified, and chemical formulae for 2071 NSOBCs peaks (82%) were determined. After exclusion of isotopic peaks, 1593 unique brominated compounds were identified and chemical formulas derived for each. Most of the compounds identified had not been previously reported and had intensities which were 100- to 1000-fold greater than the congeners of polybrominated diphenyl ethers (PBDEs). In extracts of sediments, these compounds exhibited variations in intensities (<103 to ~108), m/z values (170.9438 to 997.5217), retention times on a C18 column (1.1 to 29.52 min), and the number of Br atoms (1 to 8). Generally, compounds with greater m/z values had longer retention times and greater numbers of Br atoms. Three compounds were used in a proof-of-concept experiment to demonstrate that structures of some of the screened NSOBCs could be further predicted by combining database searching and high-resolution MS2 spectra.