In this paper a Permutation Flowshop Scheduling Problem is solved using a hybridization of the Firefly algorithm with Variable Neighborhood Search algorithm. The Permutation Flowshop Scheduling Problem (PFSP) is one of the most computationally complex problems. It belongs to the class of combinatorial optimization problems characterized as NP-hard. In order to find high quality solutions in reasonable computational time, heuristic and metaheuristic algorithms have been used for solving the problem. The proposed method, Hybrid Firefly Variable Neighborhood Search algorithm, uses in the local search phase of the algorithm a number of local search algorithms, 1-0 relocate, 1-1 exchange and 2-opt. In order to test the effectiveness and efficiency of the proposed method we used a set of benchmark instances of different sizes from the literature.