In this paper a three-terminal communication scenario where two users exchange information by employing differential binary modulation and network coding via a relay is considered. The transmission is divided into three slots in time where the first and second slots are allocated to the transmission of differential encoded data of the users. After demodulation, the relay broadcasts the bit-wise XOR-ed and differential encoded packet to the users in the third slot. The optimum detector and a simplified decision algorithm are derived based on the maximum likelihood rule. The numerical results for Rayleigh fading show that both of the proposed algorithms provide full diversity order. The simulations also demonstrate that the proposed differential network coded transmission not only offers a sum-rate gain of up to 4/3 compared to classical bi-directional relaying with four communication slots but also provides better BER performance as the signal to noise ratio increases.