The volume of petroleum produced water (PPW) has increased dramatically over the last decade. PPWs are rich in salts and often contain high concentrations of potentially toxic trace elements such as Barium (Ba), Strontium (Sr), Selenium (Se), and Arsenic (As) which, under the right circumstances, may contaminate freshwater supplies. To avoid these issues, PPW is frequently disposed of in subsurface aquifers such as the dolomitic Arbuckle Group in the state of Oklahoma, USA. This may not be a permanent solution if the injected PPW migrates within the disposal sites to ultimately reach conductive fault zones and/or existing wells with casing and/or cementing failures. In these cases the water could pose an environmental risk to potable groundwater. In order to understand the mobility of these elements under conditions similar to produced water injection, we conducted a series of batch sorption experiments. We investigated the effect of brine salinity and temperature on the sorption of Ba, Sr, Se, and As by dolomite. The results revealed that the sorption of the tested elements on dolomite did not substantially change with increasing salinity from 18 to 90 g/L. However, the sorption for all elements did increase with increasing temperature from 22 to 150 °C. This is likely due to a combination of strong surface complexation or ion exchange reactions coupled with precipitation/co-precipitation on the dolomite mineral surfaces.