Photoacoustic (PA) imaging is indeed one of the most promising bioimaging techniques for theranostics applications in humans, allowing for the visualization of blood vessels and melanomas with high spatial resolution. However, in order to overcome the endogenous contrast arising from interfering endogenous species such as haemoglobin and melanin, specific contrast agents need to be developed, allowing PAI to successfully identify targeted contrast in the range of wavelengths in which interference from the biomatrix is minimized. This has been first performed by small molecule dyes, which, however, suffer from some important limitations such as low hydrophilicity and short circulation times. For this reason, scientific research has recently directed its efforts towards the development of nanostructured contrast agents capable of providing efficient PA contrast at low concentrations with low toxicity and high biocompatibility. The principal nanostructures are based on (1) metal and semiconducting nanoparticles, amongst which variously shaped nano-gold plays the main role, (2) carbon nanomaterials, such as carbon nanotubes and graphene, and (3) conjugated polymer nanoparticles. In this review, the principal characteristics of this class of materials are reported and greater focus is directed towards in vivo studies. A detailed analysis is performed on various physical-chemical parameters that define the PA response of reported contrast agents, like absorption coefficients and photoacoustic efficiencies. By comparing the experimental data, this review provides a comprehensive tool for the evaluation of new nanostructured contrast agents for PA imaging.