A search heuristic is proposed for reverse engineering of gene regulatory networks. The approach is based on the variable neighborhood search metaheuristic. Search neighborhood structures are defined based on permissible move types. Empirically it outperforms greedy techniques in both speed and solution quality.