La paix à peine signée, Mazarin le lance contre les Barbaresques. « Le chevalier Paul partit sur son ordre avec quinze navires pour négocier avec les pirates barbaresques et obtenir la libération des Français devenus esclaves. Une personnalité aussi impétueuse n'avait guère, semblait-il, l'étoffe d'un bon négociateur, mais il parvint à racheter les rescapés d'un naufrage au pacha de Tripoli, avec lequel il conclut un traité qui sauvait la face »³. À La Goulette et à Alger, en revanche, il n'obtient rien, et le manque de vivres le ramène en France. Mazarin meurt en mars 1661 sans avoir reçu son rapport. C'est donc au roi que Paul l'adresse : il y « préconise l'emploi de bâtiments légers pour les pourchasser et la conquête d'Alger pour s'y installer à demeure »².
Le règne personnel de Louis XIV commence, et « Colbert entreprend aussitôt de restaurer la Marine ruinée par les troubles de la Fronde ; il charge Duquesne d’en faire l’inventaire : la flotte du Levant se réduit à quelques galères et celle du Ponant se limite à onze vaisseaux armés à La Rochelle et à huit navires désarmés à Brest »² [RENVOI : biographie de Duquesne]. Avec si peu, les premières campagnes ne donnent rien. Le duc de Beaufort, petit-fils d’Henri IV, en tire en 1662 une conclusion qui vise les hommes de la trempe de Paul : « Ce qui est bien nécessaire à la Marine est d’y faire entrer des gens de qualité et qui ayent du bien. Cela pare bien la marchandise et avec l’expérience de bons lieutenants le service s’en fait mieux »⁶. L’année suivante, Paul opère avec Duquesne devant Alger et Tunis, et Beaufort, qui croise sur ses vaisseaux, le juge d’une phrase : il « sert dignement mais est vieux et incommodé »⁶. Il a soixante-quatre ans.
« En 1664, le Roi décide d'appliquer les propositions du chevalier Paul et nomme Beaufort le 6 avril 1664 commandant en chef de l'armée navale »². Soixante-quatre voiles sont réunies, et le comte de Gadagne commande les troupes. Mais Paul avait désigné Alger, et c'est une autre cible qui est retenue : « Le duc de Beaufort décide d'attaquer Djidjelli, choix discutable, et prend le chevalier Paul sur la Royale comme capitaine de pavillon et conseiller technique »². Duquesne est de l'expédition, sur le Saint-Louis.
« La flotte mouille le 15 juillet à Minorque, où elle est rejointe par sept galères de Malte ; le 20 juillet l’escadre fait une diversion sur Bougie ; le 23 elle débarque les troupes près de la ville de Djidjelli canonnée par les navires et rapidement conquise au prix de quatre cents tués et blessés »². Beaufort fait fortifier la place, et l’on chante un Te Deum à Notre-Dame. La victoire est éphémère : « le corps expéditionnaire, après trois mois d’occupation, harcelé par les Kabyles, manque de tout et sous la pression des troupes épuisées est évacué le 31 octobre »². Le retour tourne au drame : le 9 novembre, la Lune, vaisseau vétuste, se brise au large de Toulon et coule en quelques minutes ; plus de cinq cents hommes des compagnies embarquées se noient.
Beaufort, humilié, prend sa revanche dès le printemps suivant. Début mars 1665, devant La Goulette, il surprend la flotte de l'amiral d'Alger, « dont le vaisseau amiral est incendié, détruit deux navires corsaires et en capture trois »². Paul reprend la mer en juillet, comme lieutenant général, sur la Royale ; Beaufort monte le Saint-Philippe. « Ayant quitté Toulon le 26 juillet, Beaufort capture le 23 août devant Cherchell (Sarcelle) trois frégates algériennes : le Palmier, le Soleil et le Croissant qui, escortées à Toulon, seront réparées et intégrées à la flotte »². Paul est alors détaché avec trois vaisseaux à la recherche de corsaires signalés autour de Pianosa, de Montecristo et de la Corse, tandis que Beaufort négocie en novembre, à La Goulette, « avec le pacha de Tunis le rachat des esclaves chrétiens »².