Twisted waveguides are promising building blocks for broadband polarization rotation in integrated photonics. They may find applications in polarization-encoded telecommunications and quantum-optical systems. In our work, we develop a rigorous modal theory for such waveguides. To this end, we define an eigenmode of a twisted waveguide as a natural generalization of the eigenmode of a straight waveguide. Using covariant approach for expressing Maxwell’s equations in helical reference frame, we obtain the eigenmode equation which appears to be nonlinear with respect to the eigenvalue, i.e. propagation constant. By analyzing the obtained equations we establish fundamental properties of the eigenmodes and prove their orthogonality. We develop a finite-difference full-vectorial scheme for solving the eigenmode equation and solve it using two approaches: with perturbation theory and using routines for nonlinear eigenvalue problems. By analyzing the obtained propagation constants and modal fields we explain the modal mechanism of polarization rotation in twisted waveguides and explain qualitatively polarization conversion efficiency dependence on twist length. Although photonic applications are of our primary concern, our results are general and apply to twisted waveguides of arbitrary architecture.