Starch has received much attention due to the advantages, such as low cost, wide availability, and excellent compostability without toxic residues. However, starch-based materials are known with limitations related to weak mechanical properties and poor long-term stability, which could be overcome by incorporation with carbonaceous nanofillers. Thus, nanobiocomposites, namely dispersion of nano-sized fillers into a starch-biopolymer matrix, is one of the most promising technological advances. The starch-based carbonaceous nanofillers not only improve the poor mechanical properties of starch, but also change the performance of carbonaceous nanofillers solubility in water. This paper reviews the state-of-the-art in the field of starch-based carbonaceous nanofillers. Two types of carbonaceous nanofillers including carbon nanotubes and graphene that have been used with starch are discussed. The main properties and applications of starch-based carbonaceous nanofillers are also discussed.