A microorganism producing carboxymethylcellulase (CMCase) was isolated from seawater, identified as Bacillus velezensis by analyses of 16S rDNA and partial sequences of the gyrA, and designated as B. velezensis A-68. The optimal conditions for production of CMCase by B. velezensis A-68 were established using response surface methodology (RSM). The optimal concentrations of rice hulls and yeast extract, and initial pH of the medium for cell growth were 60.2 g/l, 7.38 g/l, and 7.18, respectively, whereas those for production of CMCase were 50.0 g/l, 5.00 g/l, and 7.30. The analysis of variance (ANOVA) implied that the most significant factor for cell growth as well as production of CMCase was yeast extract. The optimal concentrations of $K_2HPO_4$, NaCl, $MgSO_4{cdot}7H_2O$, and $(NH_4)_2SO_4$ in the medium for cell growth were 7.50, 1.00, 0.10, and 0.80 g/l, respectively, which were the same as those for production of CMCase. The optimal temperatures for cell growth and production of CMCase were 30 and $35^{circ}C$, respectively. The maximal production of CMCase under optimized conditions was 83.8 U/ml, which was 3.3 times higher than that before optimization. In this study, rice hulls, agro-byproduct, were developed as a substrate for production of CMCase and time for production of CMCase was reduced to 3 days using a newly isolated marine bacterium.