Several problems related to networks are based on the identification of certain nodes which can be relevant for different tasks: network security and stability, protein interaction, or social influence analysis, among others. These problems can be modeled with the Critical Node Detection Problem (CNDP). Given a network, the CNDP consists of identifying a set of p nodes whose removal minimizes the pairwise connectivity of the network. In this work, a Basic Variable Neighborhood Search (BVNS) algorithm is presented with the aim of generating high quality solutions in short computing times. The detailed experimental results show the performance of the proposed algorithm when comparing it with the state of the art method, emerging BVNS as a competitive algorithm for the CNDP.