We present a robust adaptive beamforming algorithm based on the worst-case criterion and the constrained constant modulus approach, which exploits the constant modulus property of the desired signal. Similarly to the existing worst-case beamformer with the minimum variance design, the problem can be reformulated as a second-order cone (SOC) program and solved with interior point methods. An analysis of the optimization problem is carried out and conditions are obtained for enforcing its convexity and for adjusting its parameters. Furthermore, low-complexity robust adaptive beamforming algorithms based on the modified conjugate gradient (MCG) and an alternating optimization strategy are proposed. The proposed low-complexity algorithms can compute the existing worst-case constrained minimum variance (WC-CMV) and the proposed worst-case constrained constant modulus (WC-CCM) designs with a quadratic cost in the number of parameters. Simulations show that the proposed WC-CCM algorithm performs better than existing robust beamforming algorithms. Moreover, the numerical results also show that the performances of the proposed low-complexity algorithms are equivalent or better than that of existing robust algorithms, whereas the complexity is more than an order of magnitude lower.