Pollution affects all biomes. Marine environments have been particularly impacted, especially coral reefs, one of the most sensitive ecosystems on Earth. Globally, 4.5 billion people are economically dependent on the sea, where most of their livelihood is provided by coral reefs. Corals are of great importance and therefore their extinction leads to catastrophic consequences. There are several possible solutions to remediate marine pollutants and local contamination, including bioremediation. Bioremediation is the capacity of organisms to degrade contaminants. The approach presents several advantages, such as sustainability, relatively low cost, and the fact that it can be applied in different ecosystems, causing minimal impacts to the environment. As an extra advantage, the manipulation of endogenous microbiomes, including putative beneficial microorganisms for corals (pBMCs), may have probiotic effects for marine animals. In this context, the use of the two approaches, bioremediation and pBMC inoculation combined, could be promising. This strategy would promote the degradation of specific pollutants that can be harmful to corals and other metaorganisms while also increasing host resistance and resilience to deal with pollution and other threats. This method focuses on the selection of pBMCs to degrade two contaminants: the synthetic estrogen 17a-ethinylestradiol (EE2) and crude oil. Both have been reported to negatively impact marine animals, including corals, and humans. The protocol describes how to isolate and test bacteria capable of degrading the specific contaminants, followed by a description of how to detect some putative beneficial characteristics of these associated microbes to their coral host. The methodologies described here are relatively cheap, easy to perform, and highly adaptable. Almost any kind of soluble target compound can be used instead of EE2 and oil.