Toujours empressé auprès de sa femme, Paul n'est cependant pas insensible au charme d'une demoiselle d'honneur de la grande-duchesse, une certaine Catherine Nelidov, qui a la trentaine comme lui et dont l'adolescence s'est écoulée dans le célèbre Institut Smolny, pépinière de jeunes filles bien nées et bien élevées. Alors que Marie Fedorovna est grande, plantureuse et blonde, Catherine Nelidov se présente comme une petite femme brune, menue, au regard ardent et à la conversation pétillante. La comtesse Barbara Golovine, dame d'honneur également, la décrit ainsi dans ses Mémoires : « De petits yeux imperceptibles, une bouche fendue jusqu'aux oreilles et une longue taille sur de petites jambes de basset ne forment pas une figure fort attrayante. Mais elle a beaucoup d'esprit et de talent. » Marie Fedorovna apprécie la compagnie de cette jeune personne, dont les mines et les reparties la reposent de l'ennui pesant de l'étiquette. Et Paul est aussi engoué qu'elle de la nouvelle venue. La présence de Catherine Nelidov, loin de compromettre l'harmonie qui règne entre les époux, leur apporte le piment dont ils ont besoin pour agrémenter le train-train conjugal. Sans être un ménage à trois, le groupe de Leurs Altesses et de la demoiselle d'honneur forme une coalition d'inséparables, à l'abri de toute jalousie et de toute tentation perverse. Mais des témoins malveillants dénoncent cette trop bonne entente à la tsarine. Avertie des bruits qui courent à son sujet, Catherine Nelidov écrira, quelques années plus tard, au grand-duc : « Est-ce que vous êtes un homme pour moi ? Je vous jure que je ne m'en suis jamais aperçue depuis que je vous suis attachée, il me semble que vous êtes ma sœur1. » En vérité, cette atmosphère équivoque, dont aucun des trois acteurs n'analyse franchement la nature, agit sur les sens de Paul et de sa femme. Il existe ainsi des infidélités virtuelles, qui aident à conserver la fidélité réelle mieux que ne le ferait un serment prononcé à l'église. La preuve en est que, le 13 décembre 1784, moins d'un an et demi après la naissance d'Alexandra, Marie Fedorovna accouche d'une petite Hélène, c'est le quatrième enfant du couple : tandis qu'Alexandra vagit dans son berceau, Constantin et Alexandre continuent de pousser comme des chênes sous les yeux émerveillés de leur grand-mère. L'impératrice espère que sa bru, qui a les flancs si généreux, ne s'arrêtera pas là. Et, en effet, dès le 4 février 1786, les habituelles salves d'artillerie et sonneries de cloches annoncent la naissance de la troisième fille de Leurs Altesses : la grande-duchesse Marie.
Comblé dans ses vœux de paternité, Paul voudrait l'être aussi dans ses ambitions guerrières. Puisqu'il possède en toute propriété une principauté autonome au cœur de la Russie, pourquoi n'y entretiendrait-il pas un embryon d'armée qui préfigurera celle, immense, dont il assumera le commandement après son accession au trône ? En étudiant le comportement de la garde impériale, il a relevé tant de négligence, de maladresse, de favoritisme et de gabegie qu'il en est outré. Les officiers de ces unités d'élite sont plus assidus aux bals et aux spectacles qu'aux revues ; ils comptent plus sur leurs relations à la cour que sur leur valeur au combat pour obtenir un avancement. Afin de réagir, dans son domaine réservé de Gatchina, contre un laisser-aller qui menace de corrompre les plus fiers régiments de Russie, Paul fait appel à des instructeurs prussiens et les charge de rétablir l'ordre et la ponctualité parmi les soldats et les gradés cantonnés sur ses terres. Ce renouveau de l'esprit de discipline et de dévouement servira d'exemple, pense-t-il, à toutes les autres formations militaires de l'empire. En 1788, il dispose déjà de cinq bataillons. Bientôt, il aura deux mille cinq cents hommes à faire manœuvrer pour son plaisir. Ils seront dotés d'un équipement et d'une instruction radicalement différents de ceux des troupes régulières. Mois après mois, des escadrons de cavalerie et des éléments d'artillerie compléteront l'armée nouvelle.
Dans cette entreprise de retour aux « vraies valeurs », Paul est résolu à contrecarrer les dernières initiatives de son ennemi juré, le tout-puissant Potemkine. Celui-ci s'étant mis en tête de « moderniser » l'habillement des soldats, lequel datait de la guerre de Sept Ans, avait coupé les nattes, interdit la poudre dans les cheveux et imposé un uniforme commode (simple tunique et pantalon bouffant, comme on en voit chez les gens du peuple). Révolté par cet outrage à la tradition, Paul exige que ses hommes à lui aient la tête pommadée, nattée et poudrée, qu'ils portent un énorme chapeau et une courte canne, que des bottes leur enserrent les jambes jusqu'aux genoux et que des gants leur montent jusqu'aux coudes. A son avis, une certaine gêne dans la tenue des soldats ne peut que les inciter à se raidir devant le danger et à mettre plus d'ardeur dans la riposte. D'ailleurs, plus leur comportement à la parade sera sévèrement sanctionné et plus ils gagneront en efficacité sur le champ de bataille. Les officiers ont ordre de se montrer impitoyables dans le dressage de leurs subordonnés. C'est la Prusse transplantée aux abords de Saint-Pétersbourg. En passant ses troupes en revue, Paul peut se croire à Berlin, dans la peau de Frédéric II. Peu importe que les volontaires recrutés pour servir aux amusements martiaux du maître de Gatchina soient, pour la plupart, des rebuts des régiments de l'impératrice. Avec ces rustres, dont certains sont des déserteurs, des illettrés, des épaves, Paul est persuadé qu'à force de persévérance et de dureté il formera une armée invulnérable. Mordu par la tarentule du caporalisme, il veut que ces centaines de gaillards, habillés par lui de la même manière et accomplissant, en même temps, les mêmes mouvements, oublient toute identité, toute humanité, et se fondent dans un mécanisme collectif dont il serait l'âme. Pour le seconder dans son effort de mise au pas des individus au profit de la masse, il s'entoure d'officiers au gosier sonore et au cerveau étroit, qui s'appliquent à exécuter sans murmurer ses fantasmes de dompteur. Le plus exigeant, le plus obtus de ces gradés est un certain capitaine Alexis Araktcheïev, surnommé « le caporal de Gatchina ». Avec sa face desséchée, son menton osseux et ses minuscules yeux gris acier profondément enfoncés dans les orbites, il semble toujours méditer un méchant tour ou fignoler une punition machiavélique. A la fois grotesque et inquiétant, il a, selon certains, « l'air d'un singe en uniforme ». Paul apprécie sa servilité et son zèle. Il songe à en faire l'ordonnateur de toutes les activités, aussi bien civiles que militaires, après sa prise de pouvoir. Sans le dire publiquement, il est persuadé que la Russie serait à jamais sauvée si tous les citoyens étaient des soldats et toutes les maisons des casernes.
En attendant l'avènement de ce paradis de l'uniformité, il fait aménager, à Gatchina, des baraquements, des corps de garde, des écuries, des terrains de manœuvre. Sur la place réservée aux parades, les régiments répètent, durant des heures, des exercices d'alignement, de défilé par colonne, de changement de pas, de présentation d'armes et de regroupement accéléré, le tout avec la précision d'un mouvement d'horlogerie. Pendant ces exhibitions interminables, Paul, la nuque raide et la canne de commandement à la main, goûte l'ivresse de peser à lui seul plus lourd que ces milliers d'homoncules interchangeables qui passent devant lui, frappant le sol de leurs talons en cadence. Cette manifestation d'un despotisme tatillon étonne, certes, la grande-duchesse, mais ne l'inquiète pas outre mesure. Elle a souvent constaté qu'après avoir procédé à l'inspection des troupes, Paul, en retrouvant sa famille, paraît plus détendu et plus tendre qu'auparavant. Comme si cette occupation de contrôle l'avait purgé de son humiliation et de sa rancœur. Même l'impératrice, qui pourrait se formaliser du développement de quelques régiments par trop originaux en marge de son armée, ne s'en alarme nullement. Elle voit là un enfantillage, une manie de plus, que Paul aurait héritée de son père. Elle estime que cette inoffensive passion détourne le grand-duc d'idées autrement dangereuses. Il suffit parfois d'un simulacre d'autorité pour rompre, chez l'ambitieux, la soif de l'autorité véritable. Grâce à cet « amuse-gueule », Sa Majesté est sûre qu'elle n'aura pas de soucis à se faire jusqu'à la fin de ses jours.