In this work, an antimicrobial guanidine polymer (PHGH) was grafted onto starch as a carrier to form branched or grafted chains along the starch backbone. This grafting improved the antimicrobial properties and the adsorption of the starch on recycled cellulose fibers. Similar work was also conducted on bleached sulfite fibers for comparison. The results showed that the starch, grafted with 12 wt% PHGH, adsorbed more on recycled fibers than on sulfite fibers. By applying the antimicrobial-modified starch to recycled or sulfite pulps up to 20 mg/g, both antimicrobial and antimold performances of the papers were improved substantially. Additionally, the PHGH-modified starch increased the tensile index of papers, but decreased the tear index slightly. Scanning electron microscopy (SEM) and atomic force microscopy (AFM) were employed to investigate the morphologic changes of Escherichia coli bacteria and Chaetomium globosum fungi upon exposure to the PHGH-modified starch, thus demonstrating that the antimicrobial mechanism is based on the damage of bacterial membrane.