We aimed to increase the utility of Broussonetia kazinoki (paper mulberry) by using its woody parts as a substrate for Lentinula edodes cultivation. Using different mixing ratios of paper mulberry and oak tree sawdust, five types of column-type media were prepared (1.2 kg each). Two L. edodes strains (NIFoS 2462 and NIFoS 2778) were used in this study. In the first flush, numerous small mushrooms were harvested because the fruited mushrooms were densely packed on the small media. The highest productivity was obtained with a 3:1 mixture of paper mulberry and oak tree sawdust (Q. acutissima:Q. mongolica, 1:1). In particular, for NIFoS 2462, the proportion of paper mulberry in the medium positively correlated with productivity. The size of NIFoS 2778 was uniform in all media tested. By contrast, the mushroom weight of NIFoS 2462 decreased, but the other characteristics were not significantly affected. Collectively, these findings suggest that B. kazinoki sawdust could be used to grow shiitake mushrooms and that some oak sawdust substitution is also possible. Our results could increase the utility of discarded by-products, such as sawdust.