Social interaction is fundamental to our everyday life and that of diverse animals. When two animals interact, they behave in different ways. Thus, to get a full picture of the neural activity underlying each interaction, we need to record from the brains of both animals at the same time. We do so in a highly social mammal, the Egyptian fruit bat, using wireless electrophysiology, which allows unrestrained natural behaviors during recording. We recorded simultaneously from the frontal cortex of pairs of bats, as they naturally interacted with each other and engaged in a wide range of behaviors, which we characterized at a detailed level. LFP power in different frequency bands, as well as spiking activity, showed distinct behavior-dependent dynamics, which were remarkably correlated across brains at timescales that extended from seconds to tens of minutes. An increase in correlation across brains preceded the initiation of social interactions, suggesting that the correlation reflects processes that facilitate social interactions. Furthermore, we simultaneously recorded from two bats in separate, identical chambers, under a variety of conditions where the two bats received similar sensory inputs and were in similar behavioral states, and found that in the absence of direct social interactions, there was no correlation across brains. In conclusion, we have demonstrated a neural correlate of the behavioral coordination of social interactions.