To the extent that recognition memory relies on interactions among widely distributed neural assemblies across the brain, phase synchronization between brain rhythms may play an important role in meditating those interactions. As the theta rhythm is known to modulate in power during the recognition memory process, we aimed to determine how the phase synchronization of the theta rhythms across the brain changes with recognition memory. Fourteen human participants performed a visual object recognition task in a virtual reality environment. Electroencephalograms were recorded from the scalp of the participants while they either recognized objects that had been presented previously or identified new objects. From the electroencephalogram recordings, we analyzed the phase-locking value of the theta rhythms, which indicates the degree of phase synchronization. We found that the overall phase-locking value recorded during the recognition of previously viewed objects was greater than that recorded during the identification of new objects. Specifically, the theta rhythms became strongly synchronized between the frontal and the left parietal areas during the recognition of previously viewed objects. These results suggest that the recognition memory process may involve an interaction between the frontal and the left parietal cortical regions mediated by theta phase synchronization.