With the increasing spans and complex deck shapes, aerodynamic nonlinearity becomes a crucial concern in the design of long-span bridges. This paper investigates the nonlinear interaction between the gust-induced and motion-induced forces acting on bridge decks using the Vortex Particle Method (VPM) as a Computational Fluid Dynamics (CFD) method. This nonlinear interaction is complex and intractable by the conventional linear semi-analytical models that employ the superposition principle. To excite such interaction, a sinusoidally oscillating bridge deck is subjected to sinusoidal vertical gusts. Two distinct aspects are studied: The influence of large-scale sinusoidal vertical gusts on the shear layer of a moving body and the nonlinear dependence of the aerodynamic forces on the effective angle of attack. For the latter, the resultant aerodynamic forces based on a linear semi-analytical and a CFD model are compared for the same effective angle of attack due to sinusoidal gust and motion. The methodology is first employed to verify the linear behavior of a flat plate and then study the nonlinear behavior of two bridge decks. The results show that the linear superposition principle holds for streamlined bridge decks with minimal shear layer instability. However, this principle may not be valid for bluff bridge decks due to strong separation vortices that dictate the shear layer, which induces nonlinearity in the aerodynamic forces manifested through amplitude difference in the first harmonic and emergence of higher-order harmonics. The outcome of this study aims to provide a deeper understanding of the complex nonlinear fluid–structure interaction occurring for bluff bodies subjected to motion and free-stream gusts.