Nanostructures are promising candidates for use as active materials for the detection of chemical and biological species, mainly due to the high surface-to-volume ratio and the unique physical properties arising at the nanoscale. Among the various nanostructures, materials comprised of sp(2)-carbon enjoy a unique position due to the possibility to readily prepare them in various dimensions ranging from 0D, through 1D to 2D. This review focuses on the use of 1D (carbon nanotubes) and 2D (graphene) carbon nanostructures for the detection of biologically relevant molecules. A key advantage is the possibility to perform the sensing operation without the use of any labels or complex reaction schemes. Along this spirit, various strategies reported for the label-free electrical detection of biomolecules using carbon nanostructures are discussed. With their promise for ultimate sensitivity and the capability to attain high selectivity through controlled chemical functionalization, carbon-based nanobiosensors are expected to open avenues to novel diagnostic tools as well as to obtain new fundamental insight into biomolecular interactions down to the single molecule level.