Existing relational learning approaches usually work on complete relational data. However, in real-world applications, data are often incomplete. This paper proposes the MLTEC (maximum likelihood tree and evolutionary computing method) method to learn structures of the probabilistic relational models (PRMs) from incomplete relational data. The incomplete relational data are filled randomly at first, and a maximum likelihood tree (MLT) is generated from each completed data sample. This population of MLTs is then evolved through an evolutionary computing process, and the incomplete data are modified by using the best evolved structure in each generation. As a result, the probabilistic structure is learned. Experimental results show that the MLTEC method can learn good structures from incomplete relational data.