This thesis contributes to develop a new class of methods for the numerical solution of partial differential equations (PDEs) using space-time domain decomposition algorithms to ensure the use of different time steps in different subdomains. We first introduce and analyze new types of Waveform Relaxation methods based on the Dirichlet-Neumann and Neumann-Neumann methods, for parabolic and hyperbolic problems. The algorithms, formally termed as Dirichlet-Neumann Waveform Relaxation (DNWR) and Neumann-Neumann Waveform Relaxation (NNWR), generalize the use of substructuring methods to the case of evolution problems in a natural way. We finally propose an application of these methods for PDE-constrained Optimal Control Problems, solving the underlying forward and adjoint PDEs using a domain decomposition method. We apply and analyze the Dirichlet-Neumann and Neumann-Neumann methods on control problems and give the optimal choice of relaxation parameters for both the forward and adjoint problems in the steady as well as time-dependent case.