The Internet of Things (IoT) has become an important research topic in the last decade, where things refer to interconnected machines and objects with embedded computing capabilities employed to extend the Internet to many application domains. While research and development continue for general IoT devices, there are many application domains where very tiny, concealable, and non-intrusive Things are needed. The properties of recently studied nanomaterials, such as graphene, have inspired the concept of Internet of NanoThings (IoNT), based on the interconnection of nanoscale devices. Despite being an enabler for many applications, the artificial nature of IoNT devices can be detrimental where the deployment of NanoThings could result in unwanted effects on health or pollution. The novel paradigm of the Internet of Bio-Nano Things (IoBNT) is introduced in this paper by stemming from synthetic biology and nanotechnology tools that allow the engineering of biological embedded computing devices. Based on biological cells, and their functionalities in the biochemical domain, Bio-NanoThings promise to enable applications such as intra-body sensing and actuation networks, and environmental control of toxic agents and pollution. The IoBNT stands as a paradigm-shifting concept for communication and network engineering, where novel challenges are faced to develop efficient and safe techniques for the exchange of information, interaction, and networking within the biochemical domain, while enabling an interface to the electrical domain of the Internet.