CHOLESTEROL oxidase (CHO) is an oxidoreductase flavoenzyme with significant biotechnological applications. Recently, microbial CHO has received a great attention for their wide applications in medicinal field. The objective of the present work details the screening of extracellular cholesterol oxidase (CHO) producing microorganisms. Cholesterol oxidase producing bacteria were isolated from various local soil samples and some dairy products. Twelve isolates were tested for cholesterol oxidase activity using the well diffusion agar method to assess their ability to decompose cholesterol. One isolate was finally selected based on the highest productivity of cholesterol oxidase and high degree of cholesterol decomposition. The selected isolate was characterized using morphological, physical and biochemical techniques. The isolated bacterium was identified as Bacillus cytotoxicus strain and confirmed molecularly using 16S rRNA gene sequencing and deposited in GenBank with accession number KY367576. Classical (one-variable-at-a-time) and statistical method (Plackett–Burman design) were used to optimize growth medium to enhance the production of CHO from Bacillus cytotoxicus. The statistical optimized medium exhibited 2.63-fold increase in enzyme activity (2.31U/mL) and 2.57-fold increase in cholesterol decomposition (88.9%) in comparison with the un-optimized basal medium. The results revealed that Bacillus cytotoxicus has great potential for cholesterol degradation and produced significant levels of extracellular CHO in an optimized medium.