Proposed just a few years ago, Variable Neighborhood Search (VNS) is a new metaheuristic for combinatorial and global optimization, based upon systematic change of neighborhood within a possibly randomized local search. Its development has been rapid. After reviewing the basic scheme of VNS, several extensions aimed at solving large problem instances are surveyed. Issues in devising a VNS heuristic are discussed. Finally, recent applications are briefly summarized, with special attention given to VNS-based computer-aided discovery of conjectures in graph theory.