The last decade has seen the development of green materials, which intends to reduce the human impact on the environment. Green polymers are obviously tendency subset of this stream and numerous bio-sourced plastics (bioplastics) have been developed. Starch as an agro-sourced polymer has received much attention recently due to its strong advantages such as low cost, wide availability, and total compostability without toxic residues. However, despite considerable commercial products being available, the fundamental properties (mechanical properties, moisture sensitivity, etc.) of plasticised starch-based materials have to be enhanced to enable such materials to be truly competitive with traditional petroleum-based plastics over a wider range of applications. Regarding this, one of the most promising technical advances has been the development of nano-biocomposites, namely dispersion of nano-sized filler into a starch biopolymer matrix. This paper reviews the state-of-the-art in the field of starch-based nano-biocomposites. Various types of nanofillers that have been used with plasticised starch are discussed such as phyllosilicates (montmorillonite, hectorite, sepiolite, etc.), polysaccharide nanofillers (nanowhiskers/nanoparticles from cellulose, starch, chitin, and chitosan), carbonaceous nanofillers (carbon nanotubes, graphite oxide, and carbon black), and many more. The main preparation strategies for starch-based nano-biocomposites with these types of nanofillers and the corresponding dispersion state and related properties are also discussed. The critical issues in this area are also addressed.