We present a general method to efficiently design optimal control sequences for non-Markovian open quantum systems, and illustrate it by optimizing the shape of a laser pulse to prepare a quantum dot in a specific state. The optimization of control procedures for quantum systems with strong coupling to structured environments-where time-local descriptions fail-is a computationally challenging task. We modify the numerically exact time evolving matrix product operator (TEMPO) method, such that it allows the repeated computation of the time evolution of the reduced system density matrix for various sets of control parameters at very low computational cost. This method is potentially useful for studying numerous optimal control problems, in particular in solid state quantum devices where the coupling to vibrational modes is typically strong.