Recently, transformer-based trackers have become the leading approach, surpassing traditional CNN-based trackers in accuracy. However, their high computational demands hinder their deployment on edge platforms, necessitating efficient solutions. To address this, we propose a novel Neural Architecture Search (NAS) framework designed for transformer-based trackers, named NASTrack. This framework incorporates token pruning to optimize both transformer block structures and the layer-wise token keeping ratio, striking a balance between performance and efficiency. To handle the larger search space introduced by the keeping ratio, we propose a blacklist strategy and a matching-based distillation driven by the Token Overlap Ratio (TOR). Our method discovers hundreds of high-performing trackers, with FLOPs ranging from 1G to 18G. The searched trackers consistently outperform existing efficient state-of-the-art trackers such as CompressTracker and LiteTrack under comparable computational budgets.The code and models are available at https://github.com/Cyhoon84/NASTrack.git.