Carbon nanostructures such as multiwalled carbon nanotubes (CNT) and graphene (G) are potential candidates in a large number of biomedical applications. However, there is limited understanding and connection between the physicochemical properties of diverse carbon nanostructures and biological systems, particularly with regard to cellular responses. It is also crucial to understand how the structure and surface composition of carbon nanostructures affect the cellular internalization process. Here, through in vitro cellular entry kinetics and cytotoxicity studies using MCF-7 breast cancer cells and H460 human lung cancer cells, we show that the structure and surface composition of CNT and G conjugates with various molecules such as PAMAM dendrimers (G4) and G4-poly(ethylene glycol) (PEG) are directly related to their cellular internalization ability and toxicity. Interestingly, the cellular association of CNT and G nanoconjugates was observed to be structure and surface composition dependent. We found that CNT conjugates internalized more compared to G conjugates. Furthermore, G4 conjugated CNT internalized more compared to G4-PEG conjugated CNT, whereas, higher internalization was found for G4-PEG conjugated G than G4 conjugated G. We have also correlated the cytotoxicity and cellular uptake mechanisms of CNT, G, and their conjugates through zeta potential measurements, fluorescence quenching studies and by fluorescence-activated cell sorting. Altogether these studies suggest different biological activities of the carbon nanostructures, with the shape and surface composition playing a primary role.