Peptides containing the Asn-Gly-Arg (NGR) motif are known to bind CD13 isoforms expressed in tumor vessels and have been widely used for tumor targeting. Residues flanking the NGR sequence play an important role in modulating the binding affinity and specificity of NGR for the CD13 receptor. Herein, we have used a rapid, easy, and reliable peptide array–whole cell binding assay for screening a library of NGR peptides with different flanking residues. A peptide array consisting of forty-five NGR containing peptides was synthesized on a cellulose membrane, followed by screening against CD13 positive (HUVEC and HT-1080) and CD13 negative cell lines (MDA-MB-435 and MDA-MB-231). The library screening led to the identification of five cyclic and acyclic NGR peptides that display higher binding (up to 5-fold) to CD13 positive cells with negligible binding to CD13 negative cell lines when compared to the lead sequence cyclic CVLNGRMEC. Peptides with high binding affinity for the CD13 positive cells also showed improved in vitro cellular uptake and specificity using flow cytometry and fluorescence microscopy. Interestingly, the identified peptides resemble the NGR sequences present in the human fibronectin protein. These NGR peptides are promising new ligands for developing tumor vasculature targeted drugs, delivery systems and imaging agents with reduced systemic toxicity.