ETP and tank bottom sludge are two forms of effluents from oil refineries, generated more in quantity than the usable oil products. These are rich in long- and short-chain hydrocarbons and heavy metals defining a toxic composition competent to deplete the surrounding soil and water quality if discarded untreated. The unassisted decomposition of these types of sludge are time-consuming; thus, a catalyzed decomposition by virtue of natural decomposing agents could solve the matter. Features such as positive effect, low cost, lack of secondary pollution, and little environmental influence make bioremediation utilizing petroleum hydrocarbon-degrading organisms an efficient and eco-friendly technology. Cyanobacteria are recognized as biogenic contributors in oil formation and thus are supposed to have in fact a better ability to decompose oil and its derivatives. Thus, the chapter is devoted to the application and assessment of a cyanobacterial species Anabaena variabilis for its potential capacity for bioremediation of petroleum hydrocarbons.