Nanoparticle-based chemotherapy is considered to be an effective approach to cancer diagnostics and therapy in modern biomedicine. However, efficient tumor targeting remains a great challenge due to the lack of specificity, selectivity, and high dosage of chemotherapeutic drugs required. A two-step targeted drug delivery strategy (DDS), involving cancer cell pre-targeting, first with a first nontoxic module and subsequent targeting with a second complementary toxic module, is a solution for decreasing doses for administration and lowering systemic toxicity. To prove two-step DDS efficiency, we performed a direct comparison of one-step and two-step DDS based on chemotherapy loaded PLGA nanoparticles and barnase*barstar interface. Namely, we developed and thoroughly characterized the two-step targeting strategy of HER2-overexpressing cancer cells. The first targeting block consists of anti-HER2 scaffold polypeptide DARPin9_29 fused with barstar. Barstar exhibits an extremely effective binding to ribonuclease barnase with K = 10 M, thus making the barnase*barstar protein pair one of the strongest known protein*protein complexes. A therapeutic PLGA-based nanocarrier coupled to barnase was used as a second targeting block. The PLGA nanoparticles were loaded with diagnostic dye, Nile Blue, and a chemotherapeutic drug, doxorubicin. We showed that the two-step DDS increases the performance of chemotherapy-loaded nanocarriers: IC50 of doxorubicin delivered via two-step DDS was more than 100 times lower than that for one-step DDS: IC50 = 43 ± 3 nM for two-step DDS vs. IC50 = 4972 ± 1965 nM for one-step DDS. The obtained results demonstrate the significant efficiency of two-step DDS over the classical one-step one. We believe that the obtained data will significantly change the direction of research in developing targeted anti-cancer drugs and promote the creation of new generation cancer treatment strategies.