Bayesian Networks (BN) provide a robust way to represent joint probability distributions (JPD) using a direct acyclic graph (DAG) that encodes the independence between variables (nodes). Learning Bayesian networks from data is considered an NP-Hard problem, and there is no consensus on the best methods. A novel genetic algorithm (GA) has been proposed for learning BN from data. The GA is based on a proposed representation that does not allow graphs with self-loop or loops with their neighbor nodes to be represented. Furthermore, it is better at exploiting the search space since similar DAGs possess more similar representations than the conventional adjacency matrix representation. The Proposed GA was compared to six other well-established algorithms for BN structure learning using five different databases. The results suggest that the proposed GA outperforms all the other algorithms in finding A DAG more similar to the ground truth for four of the five used databases.