Recent work has demonstrated that modern text classifiers trained on Deep Neural Networks are vulnerable to adversarial attacks. There is not sufficient study on text data in comparison to the image domain. The lack of investigation originates from the challenges that authors confront in the NLP domain. Despite being extremely prosperous, most adversarial attacks in the text domain ignore the overhead they induced on the victim model. In this paper, we propose a Query-efficient Black-box Adversarial Attack on text data that tries to attack a textual deep neural network by considering the amount of overhead that it may produce. We show that the proposed attack is as powerful as the state-of-the-art adversarial attacks while requiring fewer queries to the victim model. The evaluation of our method proves the promising results.