Network coding (NC) is a technique used to improve wireless networks throughput, efficiency, and scalability. When employing this technique, wireless nodes collect several packets and combine them together in one single transmission. This technique is used to attain the maximum possible network flow with minimum number of transmissions. COPE, OpNC and FENC are widely known approaches in network coding that vary in complexity and optimality. COPE is the first proposed approach for network coding that is considered as a complex approach and may lead to a packet deadline termination; thus, transmitter should resend packets, and therefore, the overall throughput decreases. OpNC employs the COPE approach in order to find all possible codes for a set of packets, brute force searching, hence it is an exhaustive approach where the optimal solution is not always reachable. On the other hand, FENC utilizes division and conquers technique, in order to find an optimal network coding of a set of native packets, in which a repetitive algorithm is applied on the output queue more than once, in order to increase the possibility of finding an optimal coding solution. In this paper, we propose a novel technique which utilizes two basic concepts of network coding: matrix optimization and the notion of conflict between packets. This technique is called “Conflict based Matrix Optimization for Network Coding Enhancement” (CMO-NCE), in which the opportunity of recovering more packets within the transmitted encoded packets combination is increased. Our proposed technique chooses better packets combination when transmitting the encoded stream; consequently, more packets are recovered at destination nodes. Simulation results show that the proposed technique is better in terms of complexity and optimality than other existing techniques such as COPE and OpNC. Also, it shows that the proposed CMO-NCE mechanism results are close to FENC approach. However, CMO-NCE’s time complexity is less than FENC and it is linear, O(n), where n is number of wireless nodes, while FENC’s time complexity is not linear, O(P^2/log2P ), where P is number of packets.