The cyclic bandwidth problem (CBP) is a significant and challenging graph labeling problem with many real-world applications, including VLSI design, interconnection networks of parallel computers, and constraint satisfaction problems. Existing methods in the literature for solving the CBP still have room for improvement on large-scale instances. To address this issue and effectively solve the CBP, we present a novel multi-start variable neighborhood tabu search (MVNTS) algorithm with a greedy construction procedure and a reload strategy. Specifically, our algorithm employs tabu strategy and two types of neighborhoods—sampled and complete—to extensively explore the solution space. Moreover, the restart and reload strategies are used to ensure the trade-off between intensification and diversification of the search while increasing the scalability of the algorithm. Extensive experiments on 202 public benchmark instances demonstrate that MVNTS outperforms the state-of-the-art algorithms in the literature in terms of both solution quality and computational efficiency.