Despite the widespread availability of immunohistochemical and other methodologies for screening and early detection of lung and breast cancer biomarkers, diagnosis of the early stage of cancers can be difficult and prone to error. The identification and validation of early biomarkers specific to lung and breast cancers, which would permit the development of more sensitive methods for detection of early disease onset, is urgently needed. In this paper, ultra-small and bright nanoprobes based on quantum dots (QDs) conjugated to single domain anti-HER2 (human epidermal growth factor receptor 2) antibodies (sdAbs) were applied for immunolabeling of breast and lung cancer cell lines, and their performance was compared to that of anti-HER2 monoclonal antibodies conjugated to conventional organic dyes Alexa Fluor 488 and Alexa Fluor 568. The sdAbs-QD conjugates achieved superior staining in a panel of lung cancer cell lines with differential HER2 expression. This shows their outstanding potential for the development of more sensitive assays for early detection of cancer biomarkers.