Graph Neural Networks (GNNs) have attracted significant research interest in various graph data modeling tasks. To advance trustworthy, reliable, and safe Artificial Intelligence (AI) systems for practical applications, adversarial robustness learning on GNNs has drawn widespread attention among researchers. Numerous attack methods, including white-box attacks, gray-box attacks, and black-box attacks, have been proposed, but black-box attacks are widely considered to be the most challenging and practical in real-world applications. In this paper, we focus on the challenging and realistic black-box attack scenario on GNNs, where the attacker has no information about the structure and parameters of the target model. We first theoretically demonstrate that the loss changes of the GNNs are related to the node voting matrix, which is subject to the graph topology information and is independent to the structures of GNNs. Then, we propose a novel black-box attack strategy for GNNs based on the theoretical results, i.e., node voting influence-based GNNs black-box adversarial attack, named VoteAttack. Specifically, the VoteAttack algorithm iteratively chooses a group of significant nodes based on mutual voting among nodes (the node voting matrix) and considers the voting weights among nodes. Furthermore, the VoteAttack algorithm modifies the attributes of the selected nodes to create a perturbed graph and ultimately utilizes the perturbed graph to attack GNNs. Experimental results on popular GNNs and graph datasets indicate that the proposed attack strategy outperforms baseline strategies.