National Aeronautics and Space Administration’s Asteroid Redirect Mission (ARM) aims to capture a Near Earth Orbit (NEO) asteroid or a piece of a large asteroid and transport it to the Earth-Moon system. In this paper, we provide a detailed analysis of one of the main control challenges for the first ARM mission concept, namely despinning and three-axis stabilizing the asteroid and spacecraft combination after the ARM spacecraft captures the tumbling NEO asteroid. We first show that control laws, which explicitly use the dynamics of the system in their control law equation, encounter a fundamental limitation due to modeling uncertainties. We show that in the presence of large modeling uncertainties, the resultant disturbance torque for such control laws may well exceed the maximum control torque of the conceptual ARM spacecraft. We then numerically compare the performance of three viable control laws: the robust nonlinear tracking control law, the adaptive nonlinear tracking control law, and the simple derivative plus proportional-derivative linear control strategy. We conclude that under very small modeling uncertainties, which can be achieved using online system identification, the robust nonlinear tracking control law guarantees exponential convergence to the fuel-optimal reference trajectory and hence consumes the least fuel. On the other hand, in the presence of large modeling uncertainties, measurement errors, and actuator saturations, the best strategy for stabilizing the asteroid and spacecraft combination is to first despin the system using a derivative (rate damping) linear control law and then stabilize the system in the desired orientation using the simple proportional-derivative linear control law. More- over, the fuel consumed by the conceptual ARM spacecraft using these control strategies is upper bounded by 300 kg for the nominal range of NEO asteroid parameters. We conclude this paper with specific design guidelines for the ARM spacecraft for efficiently stabilizing the tumbling NEO asteroid and spacecraft combination.