Cell-based aptamer selection (Cell-SELEX) against predefined protein targets that benefits using the native form of the targets is the most promising approach to achieve aptamer probes capable of recognizing targets under both in vitro and in vivo conditions. The major disadvantages in Cell-SELEX are the imperfectness of the negative selection step and the lengthy procedure of selection. Here, we introduced the Counter-SELEX as part of our modified Cell-SELEX and implemented deep sequencing to overcome these shortcomings in developing aptamers against aspartate β-hydroxylase (ASPH) as a known tumor marker. In parallel with the conventional Cell-SELEX, five consecutive cycles of counter selection were accomplished using sequences bound to negative cells (the Counter-SELEX) to detect oligos that are not specific for ASPH. After high-throughput sequencing, the representative of each promising achieved family was subjected to further confirmatory analysis via flow cytometry, followed by the fluorescence immunostaining of histopathological sections. Implementing our innovative complementary method, annoying mis-selected sequences in Cell-SELEX enriched pools were effectively identified and removed. According to the affinity assay on the cells displaying ASPH, three aptamers, AP-Cell 1, AP-Cell 2, and AP-Cell 3, with values of 47.51, 39.38, and 65.23 nM, respectively, were obtained, while AP-Cell 1 and 3 could then successfully spot ASPH displayed on the tissues. Our study showed that the Counter-SELEX could be considered as a complementary method for Cell-SELEX to overcome the imperfectness of the negative selection step. Moreover, high-throughput nucleotide sequencing could help to shorten the overall process.