We propose a branch-and-bound algorithm for robust rigid registration of two point clouds in the presence of a large number of outlier correspondences. For this purpose, we consider a maximum consensus formulation of the registration problem and reformulate it as a (large) maximal clique search in a correspondence graph, where a clique represents a complete rigid transformation. Specifically, we use a maximum clique algorithm to enumerate large maximal cliques and a fitness procedure that evaluates each clique by solving a least-squares optimization problem. The main advantages of our approach are 1) it is possible to exploit the cutting-edge optimization techniques employed by current exact maximum clique algorithms, such as partial maximum satisfiability-based bounds, branching by partitioning or the use of bitstrings, etc.; 2) the correspondence graphs are expected to be sparse in real problems (confirmed empirically in our tests), and, consequently, the maximum clique problem is expected to be easy; 3) it is possible to have agoodcontrol of suboptimality with a k-nearest neighbor analysis that determines the size of the correspondence graph as a function of$k$. The new algorithm is calledCliRegand has been implemented in C++. To evaluateCliReg, we have carried out extensive tests both on synthetic and real public datasets. The results show thatCliRegclearly dominates the state of the art (e.g.,RANSAC,FGR, andTEASER++) in terms of robustness, with a running time comparable toTEASER++andRANSAC. In addition, we have implemented a fast variant calledCliRegMutualthat performs similarly to the fastest heuristicFGR.