The present study was aimed at isolation of cellulolytic microbial strains from decaying agro wastes and optimizing the environmental parameters including culture media, temperature and pH for their mass cultivation. Also, their cellulolytic potential on locally available substrates was assessed. Five efficient cellulolytic microbial strains labeled as St-01, St-03, St-04, St-07 and St-18 were selected from a total of thirty five cellulose degraders. From the investigation, it was found that Nutrient Agar with cellulose powder as a substrate, Nutrient Agar with Carboxymethylcellulose (CMC) as a substrate and Stanier’s Basal medium were found to be the most suitable media for luxuriant growth of all the selected strains at pH 7 and temperature 37°C. The assessment of their cellulolytic potential on locally available substrates proved that the grated vegetable stalk was most suitable substrate for degradation compared to straw powder and wood powder. Under similar physical and chemical conditions, the highest cellulolytic potential was exhibited by the isolate St-01 followed by the isolate St-07. The isolate St-01 was identified as Streptomyces albospinus (MTCC No. 8768); and the isolate St-07 was identified as Streptomyces somaliensis (MTCC No. 8769) at Microbial Type Culture Collection and Gene Bank, Institute of Microbial Technology, Chandigarh.