Recurrent Neural Networks (RNNs) are a major class of artificial neural networks. Designing the architecture of a Deep RNN (DRNN) together with suitable hyper-parameters for any learning task can be very time-consuming and requires expert domain knowledge. Trial-and-error methods for DRNN design have been proven to be laborious and highly costly in practice. Therefore, an efficient automatic architecture search technique is needed to design DRNNs. Most of the proposed methods based on Evolutionary Computation (EC) techniques are searching standard RNNs, but not suitable for DRNN, which is recently gaining increasing attention. DRNNs learn feature representations at higher levels of abstraction. Properly training the connection weights is very important for any DRNNs to be really useful. The overall goal of this research work is to develop advanced EC methods for designing and training DRNNs. Moreover, the focus of this research is to explore a Genetic Algorithm based method to design suitable architectures of DRNNs, Evolutionary Strategy to effectively train the connection weights, and Surrogate techniques to reduce the time to evolve DRNNs.