The number of published results in biology and medicine is growing at an exceeding rate, and thus, extracting relevant information for building useful models is becoming very laborious. Furthermore, with the newly published information, previously built models need to be extended and updated, and with the voluminous literature, it is necessary to automate the model extension process. In this work, we introduce a methodology for extending logical models of cell signaling networks using a Genetic Algorithm (GA). The proposed procedure is developed to optimally search for a subset of biological interactions that extend logical models while preserving their desired behavior. To evaluate the effectiveness of the proposed methodology, we randomly removed a subset of elements from an existing T cell differentiation model, and mixed them with randomly created interactions to mimic the output of literature reading. We then used the GA to search for the extensions that optimally reconstructed the model. The simulation results showed that the GA was able to find a set of extensions that preserved the desired behavior of the model with fewer elements than the original model. The results demonstrate that the GA is an efficient tool for model extension, and suggest that it can be used for model reduction as well.