In the design of super-long-span bridges, the wind actions are commonly a governing criterion. Critical design checks for wind-induced vibrations involve experimental and numerical procedures for determination of the flutter instability threshold, commonly under laminar free-stream. The influence of free-stream turbulence on the critical flutter velocity of bridge decks still represents an open topic in bridge aerodynamics. This paper presents an investigation of the influence of free-stream deterministic gusts on the critical flutter velocity using Computational Fluid Dynamics (CFD). Deterministic free-stream harmonic gusts are simulated by modelling the wake of two flapping airfoils using the two-dimensional Vortex Particle Method (VPM). These gusts are then applied to a streamlined bridge deck and the oscillation amplitudes are studied for various gust amplitudes and frequencies. The results indicate that the critical flutter velocity is reduced for harmonic gusts with a frequency similar to the critical frequency under laminar free-stream, while it is not in affect for gust frequencies corresponding to the structural frequencies. By dissecting the random free-stream into harmonic gusts, this study aims to provide a deeper understanding of the physical processes occurring in the fluid-structure interaction near the instability threshold.