We have little understanding of how fish hold station in unsteady flows. Here, we investigated the effect of flow speed and body size on the kinematics of rainbow trout Kármán gaiting behind a 5 cm diameter cylinder. We established a set of criteria revealing that not all fish positioned in a vortex street are Kármán gaiting. By far the highest probability of Kármán gaiting occurred at intermediate flow speeds between 30 and 70 cm s-1. We show that trout Kármán gait in a region of the cylinder wake where the velocity deficit is about 40% of the nominal flow. We observed that the relationships between certain kinematic and flow variables are largely preserved across flow speeds. Tail-beat frequency matched the measured vortex shedding frequency, which increased linearly with flow speed. Body wave speed was about 25% faster than the nominal flow velocity. At speeds where fish have a high probability of Kármán gaiting, body wavelength was about 25% longer than the cylinder wake wavelength. Likewise, the lateral (i.e. cross-stream) amplitude of the tail tip was about 50% greater than the expected lateral spacing of the cylinder vortices, while the body center amplitude was about 70% less. Lateral body center acceleration increased quadratically with speed. Head angle decreased with flow speed. While these values are different from those found in fish swimming in uniform flow, the strategy for locomotion is the same; fish adjust to increasing flow by increasing their tail-beat frequency. Body size also played a role in Kármán gaiting kinematics. Tail-beat amplitudes of Kármán gaiting increased with body size, as in freestream swimming, but were almost three times larger in magnitude. Larger fish had a shorter body wavelength and slower body wave speed than smaller fish, which is a surprising result compared with freestream swimming, where body wavelength and wave speed increased with size. In contrast to freestream swimming, tail-beat frequency for Kármán gaiting fish did not depend on body size and was a function of the vortex shedding frequency.