The alliance between Mazarin and Cromwell between 1655 and 1658 was, as François Saulnier has recently argued, ‘une alliance des contraires’ (‘Cromwell et Mazarin’ 233). This paper will explore the diplomacy that led up to the two treaties between Mazarin and Cromwell in November 1655 and March 1657, and that then surrounded the operation of that alliance in practice until Cromwell’s death in September 1658. I will examine in particular the dilemma of two leaders of different faiths, who negotiated with each other despite their religious differences, and who ultimately achieved an alliance. This involved overcoming, or at least neutralising, particular issues of concern, such as English treatment of Catholics, and French treatment of Huguenots, and focusing instead on areas of shared strategic interest, especially the benefits of an alliance against Spain. How, in short, were two such apparently contrasted powers as a Catholic monarchy recovering from the Frondes, and a Protestant republic created in the wake of the execution of Charles I, able to make common cause?