Recently, several deep learning approaches have been proposed for point cloud registration. These methods train a network to generate a representation that helps to find matching points in two 3D input point clouds. Finding good matches allows them to calculate the transformation between the two point clouds accurately. Two challenges of these techniques are dealing with occlusions and generalizing to objects of classes unseen during training. This work proposes DeepBBS, a novel method for learning a representation that takes into account the best buddy distance between points during training. Best Buddies (i.e., mutual nearest neighbors) are pairs of points nearest to each other. The Best Buddies criterion is a strong indication for correct matches that, in turn, leads to accurate registration. Our experiments show improved performance compared to previous shape registration methods. In particular, our learned representation leads to an accurate registration for partial shapes and in unseen categories.