Electrochemical immunosensors are affinity-based biosensors characterized by several useful features such as specificity, miniaturizability, low cost and simplicity, making them very interesting for many applications in several scientific fields. One of the significant issues in the design of electrochemical immunosensors is to increase the system’s sensitivity. Different strategies have been developed, one of the most common is the use of nanostructured materials as electrode materials, nanocarriers, electroactive or electrocatalytic nanotracers because of their abilities in signal amplification and biocompatibility. In this review, we will consider some of the most used nanostructures employed in the development of electrochemical immunosensors (e.g., metallic nanoparticles, graphene, carbon nanotubes) and many other still uncommon nanomaterials. Furthermore, their diagnostic applications in the last decade will be discussed, referring to two relevant issues of present-day: the detection of tumor markers and viruses.