We develop a Lagrangian perturbation framework for rotating non-relativistic superfluid neutron stars. This leads to the first generalization of classic work on the stability properties of rotating stars to models that account for the presence of potentially weakly coupled superfluid components. Our analysis is based on the standard two-fluid model expected to be relevant for the conditions that prevail in the outer core of mature neutron stars. We discuss the implications of our results for dynamic and secular instabilities of a simple neutron star model in which the two fluids are allowed to assume different (uniform) rotation rates.