Issu d’une famille noble de Champagne, il est dans sa jeunesse condamné à la prison pour une offense vénielle. Il est libéré sur les instances de la duchesse d'Orléans (1677 – 1749), fille légitimée de Louis XIV et de madame de Montespan. La duchesse est l’épouse du futur régent Philippe d'Orléans. Elle est ainsi une protectrice bien en cour.
En 1709, Lestocq arrive à Saint-Pétersbourg en qualité de médecin de cour. Il est bien considéré par Catherine Ire jusqu’en 1720, date à laquelle son mari l’exile à Kazan pour avoir séduit la fille de son bouffon. À la mort du tsar, Catherine rappelle son médecin favori à Saint-Pétersbourg, où son caractère insouciant l’amène à se lier d’amitié avec la fille de Catherine, Élisabeth, dont il est dit qu’il la guérit de sa syphilis.
Plus que quiconque, Lestocq concourt à préparer le coup d'État de 1741 qui amène Élisabeth sur le trône. Il façonne les actions d’Élisabeth en se conformant aux avis de l’ambassadeur français le marquis de La Chétardie et de l’ambassadeur suédois, qui se montrent particulièrement intéressés au renversement du régime d’Anna Léopoldonvna, la France cherchant à contrebalancer l’influence autrichienne à la Cour de Russie et la Suède étant en guerre contre la Russie à ce moment-là.
Après le couronnement d’Élisabeth, Lestocq et La Chétardie tentent de monopoliser le pouvoir d’État. Le médecin reçoit une pension de 15 000 livres du roi de France et cherche à influencer la politique étrangère de la Russie en fonction des visées de ses commanditaires. Un autre bénéficiaire des intrigues de Lestocq est le roi de Prusse, Frédéric le Grand, qui persuade même l’empereur Charles VII de le créer comte impérial. En 1743, Lestocq ourdit la conspiration de Lopoukhina de manière à provoquer la chute du chancelier Alexis Bestoutchev. C’est lui qui suggère le nom de Sophie Augusta Fredericka d’Anhalt-Zerbst (qui par son mariage allait devenir Catherine la Grande), une protégée prussienne, comme épouse pour l’héritier présomptif.
En 1745 Bestoutchev, toujours au pouvoir, réussit à intercepter la correspondance de Lestocq avec La Chétardie, ce qui aboutit à l’expulsion de Russie de ce dernier. Trois ans après, Lestocq, qui a continué d’intriguer contre Bestoutchev, est accusé de conspirer pour détrôner Élisabeth en faveur de l’héritier prussophile au trône. Il est soumis à la torture dans la Chancellerie secrète et condamné à mort. L’impératrice intercède et le fait expulser d’abord vers Ouglitch puis à Veliki Oustioug. Ce n’est qu’après la mort de la souveraine que Lestocq est restauré dans ses possessions et autorisé à rentrer dans la capitale impériale russe.
