A central challenge for implementing quantum computing in the solid state is decoupling the qubits from the intrinsic noise of the material. We investigate the implementation of quantum gates for a paradigmatic, non-Markovian model: A single qubit coupled to a two-level system that is exposed to a heat bath. We systematically search for optimal pulses using a generalization of the novel open systems Gradient Ascent Pulse Engineering (GRAPE) algorithm. We show and explain that next to the known optimal bias point of this model, there are optimal shapes which refocus unwanted terms in the Hamiltonian. We study the limitations of controls set by the decoherence properties. This can lead to a significant improvement of quantum operations in hostile environments.