We consider a general nonlinear time-delay system with state-delays as control variables. The problem of determining optimal values for the state-delays to minimize overall system cost is a non-standard optimal control problem – called an optimal state-delay control problem – that cannot be solved using existing optimal control techniques. We show that this optimal control problem can be formulated as a nonlinear programming problem in which the cost function is an implicit function of the decision variables. We then develop an efficient numerical method for determining the cost function’s gradient. This method, which involves integrating an auxiliary impulsive system backwards in time, can be combined with any standard gradient-based optimization method to solve the optimal state-delay control problem effectively. We conclude the paper by discussing applications of our approach to parameter identification and delayed feedback control.