We investigate the influence of the ellipticity of a columnar vortex in a rotating environment on its linear stability to three-dimensional perturbations. As a model of the basic-state vorticity distribution, we employ the Stuart steady-state solution of the Euler equations. In the presence of background rotation, an anticyclonic vortex column is shown to be strongly destabilized to three-dimensional perturbations when background rotation is weak, while rapid rotation strongly stabilizes both anticyclonic and cyclonic columns, as might be expected on the basis of the Taylor–Proudman theorem. We demonstrate that there exist three distinct forms of three-dimensional instability to which strong anticyclonic vortices are subject. One form consists of a Coriolis force modified form of the ‘elliptical’ instability, which is dominant for vortex columns whose cross-sections are strongly elliptical. This mode was recently discussed by Potylitsin & Peltier (1998) and Leblanc & Cambon (1998). The second form of instability may be understood to constitute a three-dimensional inertial (centrifugal) mode, which becomes the dominant mechanism of instability as the ellipticity of the vortex column decreases. Also evident in the Stuart model of the vorticity distribution is a third ‘hyperbolic’ mode of instability that is focused on the stagnation point that exists between adjacent vortex cores. Although this short-wavelength cross-stream mode is much less important in the spectrum of the Stuart model than it is in the case of a true homogeneous mixing layer, it nevertheless does exist even though its presence has remained undetected in most previous analyses of the stability of the Stuart solution.