Ecological concerns have resulted in a renewed interest in environmental-friendly composites issues for sustainable development as a biodegradable renewable resource. In this work we used cellulose fibers from recycled newspaper as reinforcement for thermoplastic starch in order to improve its mechanical, thermal and water resistance properties. The composites were prepared from corn starch plasticized by glycerol (30% wt/wt of glycerol to starch) as matrix that was reinforced with micro-cellulose fibers, obtained from used newspaper, with fiber content ranging from 0 to 8% (wt/wt of fibers to matrix). Physical properties of composites were determined by mechanical tensile tests, differential scanning calorimetry, thermogravimetric analysis, water absorption measurement and scanning electron microscopy. The results showed that higher fibers content raised the tensile strength and elastic modulus up to 175% and 292%, respectively, when compared to the non-reinforced thermoplastic starch. The addition of the fibers improved the thermal resistance and decreased the water absorption up to 63%. Besides, scanning electron microscopy illustrated a good adhesion between matrix and fibers. These results indicated that thermoplastic starch reinforced with recycled newspaper cellulose fibers could be fruitfully used as commodity plastics being strong, cheap, abundant and recyclable.