Recently we proposed a state-space model with time delays for gene regulatory networks. Although the system can be uniquely determined under some assumptions, the solution space is still too large to use an exhaustive search method to find the optimal solution. This work employs Boolean variables to capture the existence of the discrete time delays of the regulatory relationships among the internal variables, and proposes a genetic algorithm (GA) to determine the optimal Boolean variables (the optimal solution) and to further infer gene regulatory networks with time delays. Computational experiments performed on a real gene expression dataset show that GA is effective at finding the optimal solution. Not only does the regulatory network with time delay obtained from the dataset possesses the expected properties of a real one, but the approach also improves the prediction accuracy by 72%, compared to gene regulatory network without time delays.