Malgré un physique qui ne s'y prêtait guère, calvitie et emponboint, Willy passait pour être un véritable Don Juan. Ce prestige du séducteur était, en outre, rehaussé par le charme conquérant que lui conférait son immense notoriété. On imagine alors l'effet que produisit l'annonce de son mariage avec Sidonie Gabrielle Colette, au printemps de 1893 : « Willy marié ! La nouvelle avait couru comme le feu. Des théâtres aux salles de concert, des salles de rédaction aux banquettes du Napolitain, du Wéber, du Pousset, elle enjambait la Seine et se répandait au Quartier Latin, sur les buveurs du Vachette et du d'Harcourt », rappelle Marie-Jeanne Viel dans Paris-Presse l'Intransigeant du 7 mars 1957. Effectivement la nouvelle avait de quoi ébranler le Tout-Paris de la Belle Époque, et ce d'autant que la jeune mariée était une parfaite inconnue. Comment donc Sidonie Gabrielle Colette, domiciliée à Châtillon-Coligny dans le Loiret, avait-elle eu l'occasion de connaître le grand journaliste parisien ? Et comment ce dernier en vint-il à fréquenter suffisamment la jeune femme pour la demander en mariage ? Autant de questions qui, aujourd'hui encore, sont sujet à controverses.

La thèse la plus répandue veut que la rencontre des deux époux ait été favorisée par les liens que le Capitaine Colette et Jean-Albert Gauthier Villars avaient conservés de leur passé militaire. C'est à Colette elle-même que l'on doit cette version des faits. Dans Noces elle dit avoir « voué une tendre admiration au prestigieux journaliste très parisien que l'on sait, fils d'un camarade de promotion de [s]on père. » Le terme « camarade » est pour le moins contestable. De fait, Jules Colette est entré à Saint-Cyr à la fin de l'année 1847 et Jean-Albert Gauthier Villars à l'École Polytechnique en 1848, une année sépare donc leurs deux promotions. S'il est avéré, par ailleurs, qu'ils prirent part tous deux aux campagnes de Crimée et d'Italie, rien ne prouve qu'ils s'y rencontrèrent. Certains biographes allèguent que les deux hommes étaient membres de la Société de géographie, et qu'à ce titre le Capitaine remettait à Jean-Albert Gauthier-Villars des cartes qu'il réalisait lui-même. Or, si le nom du Capitaine Colette se trouve bien dans les archives de cette Société, celui de Gauthier-Villars en est absent. Il semble bien plutôt que le rapprochement entre les deux familles se fit à la librairie Gauthier-Villars, sise au 55, quai des Grands-Augustins. C'est du moins ce que révèlent des notes inédites écrites par Pierre Varenne, un des plus fidèles amis de Willy. Dans ces notes, on apprend que le Capitaine, accompagné de sa fille, se rendit un jour à la librairie Gauthier-Villars pour acheter des livres de science. Il y fut reçu par Willy à qui il conte l'histoire de sa jambe perdue à la bataille de Melegnano. Willy lui demande alors s'il n'y a pas connu son père, le Capitaine acquiesce, et Willy s'en va chercher son père qui, pour sa part, ne reconnaît absolument pas le visiteur. Peu importe, leurs souvenirs communs les rapprochent et suffisent à tisser des liens amicaux entre les deux hommes. C'est au cours de l'été de 1889, année de l'Exposition universelle, que cette première rencontre aurait eu lieu, et que, selon Pierre Varenne, Colette serait tombée sous le charme de Willy. Ce dernier a pu être séduit également, mais pour l'heure il ne songe probablement pas à engager une quelconque relation avec la jeune Gabrielle.

En ces années de gloire, la vie sentimentale d'Henry Gauthier-Villars était autrement plus amère et éprouvante que ne le laissait penser sa réputation d'auteur gai. Il avait engagé une liaison avec Marie Servat, une femme mariée dont le divorce n'était pas encore prononcé. Le couple avait toutefois élu domicile au 22, rue de l'Odéon où naîtra bientôt un petit garçon que l'on prénomme Jacques. Mais la tranquillité de ce couple idyllique allait bientôt vaciller. Atteinte d'une grave maladie, Marie s'éteint le 31 décembre 1891. Âgé de trente-deux ans, Willy se retrouve père célibataire. Une situation trouble donc qui se complique du silence qu'il avait gardé sur la naissance de son fils. Il prend alors la décision de placer l'enfant en nourrice à Châtillon-Coligny sous la protection d'Achille Robineau-Duclos (le fils aîné de Sido) qui, en sa qualité de médecin-chef du canton, a pour mission d'inspecter les nourrices. C'est donc lui qui se charge de placer l'enfant près des Colette. C'est ce que Sido explique à sa fille Juliette dans une lettre datée du 24 janvier 1892 : « Mr Gauthier-Villars est arrivé le 7 avec… son petit garçon. Il l'a mis en nourrice tout à côté de chez moi et sous la protection d'Achille. » Voilà qui prouve qu'entre la première rencontre de l'été 1889 et ce mois de janvier 1892 les relations tissées entre les deux familles se sont poursuivies et profondément affermies, sinon comment expliquer la décision de Willy ? Toujours est-il que dans cette même lettre Sido exprime clairement les ambitions qu'elle projette sur Willy : « C'est cet enfant [Jacques] qui doit faire entrer par la ‘‘grande porte'' Gabri dans la famille Gauthier-Villars parce que le grand-père est fou de ce petit et il faudra qu'il consente au mariage de son fils avec une jeune fille sans dote à cause de ce petit, sans cela je crois qu'il faudrait les sommations respectueuses. » Ce raisonnement peut laisser perplexe : si l'on comprend aisément que cette union permettrait aux Colette de bien « placer » leur fille, comme on le disait alors, on peut s'étonner qu'en janvier 1892, à peine un mois après la disparition tragique de Marie Servat, Willy songe à se marier.

Trois mois plus tard, en avril 1892, Gabrielle Colette va séjourner trois semaines à Paris, chez Madame Cholleton, la veuve du général Claude Cholleton, ancien compagnon d'armes du Capitaine. Un soir, Willy l'emmène au théâtre puis à la brasserie Pousset. Grisée par le vin d'Asti, Gabrielle lui aurait alors révélé ses sentiments dans un style pour le moins enflammé : « Je mourrai si je ne suis pas ta maîtresse. » Cette version des faits, qui trouvera une exacte correspondance dans Claudine à Paris , sera celle que Willy continuera à exposer dans les années vingt. Si rien ne confirme cette anecdote, il est du moins certain que ce séjour contribua à rapprocher les jeunes gens, et que c'est à ce moment qu'un projet de fiançailles s'est dessiné. Car le 28 novembre, Sido informe Juliette que Gabrielle se rend à Paris avec le Capitaine pour « être présentée à la famille G. Villars. » Et quelques temps plus tard, en décembre, Sido apprend à Juliette que « Gabri revient ce soir. […] Willy lui a fait la surprise de lui montrer son futur appartement tout emménagé jusqu'aux casseroles rangées et brillantes comme si on allait faire la cuisine dedans demain. » Il semble donc que l'on s'achemine lentement vers une union heureuse. Pourtant, le mariage de Colette et Willy ne se fit pas sans une certaine agitation, allant jusqu'à déclencher des actes de malveillance tels qu'il faudra lancer la rumeur de leur rupture. C'est ce que Sido explique à Juliette dans sa lettre du 28 novembre : « Non, on n'a plus reçu de lettres anonymes. Je crois que la rupture supposée du mariage a dû satisfaire la personne qui les commettait. » Et dans sa lettre suivante : « Mais si, on a encore envoyé des lettres anonymes à Willy et moi-même, j'en ai reçu une sous forme de coupure de journal où on abîmait Willy, mais toujours expédiées de Roubaix ! » La même malveillance se propage dans les colonnes des journaux, et le 4 mai 1893, deux semaines avant le mariage, le Gil Blas fait paraître un entrefilet venimeux : « On jase beaucoup à Châtillon, du flirt intense dont un de nos plus spirituels clubmen parisiens, poursuit une exquise blonde, célèbre dans toute la contrée par sa merveilleuse chevelure. On ne dit pas que le mot mariage ait été prononcé. Aussi nous engageons fort la jolie propriétaire de deux invraisemblables nattes dorées à n'accorder ses baisers, suivant le conseil de Méphistophélès, que ‘‘la bague au doigt.'' » En dépit de toutes ces médisances, le mariage sera célébré à Châtillon-Coligny, le 15 mai 1893. Dans la correspondance qu'il échange alors avec son frère, Willy ne se montre guère enthousiaste : « J'épouse la fille du Capitaine Colette (de Châtillon), heureux de témoigner ma reconnaissance à une famille qui a été, pour Jacques, d'une bonté absolument touchante. Elle n'a pas de dot, d'ailleurs, ce qui ne réjouit pas nos Parents. […] Je ne fais pas, oh non ! un mariage d'argent. Que si je m'interroge, pour savoir jusqu'à quel point j'ai le droit de prononcer le mot ‘‘mariage d'amour'' je me répondrai peut-être non, aussi. » Et ceci encore dans la lettre suivante : « Enfin, tu dis que je me marie sans grande joie. – Tu as raison, c'est vrai, je n'y peux rien, tout le monde croit que je me suis secoué les oreilles comme un chien mouillé, après le coup que j'ai reçu, et que tous jugent oublié ; c'est peut-être un peu faux. » Le coup en question, c'est bien sûr la disparition subite de Marie Servat qui laissa effectivement Willy dans une grande affliction. Mais il n'est pas si sûr en revanche que Willy ne fit un mariage d'amour en épousant la jeune Gabrielle. Car dans une lettre adressée à Marcel Schwob, ce même printemps 1893, il se dit heureux d'être à Châtillon, « songeant au mariage et tout à fait abruti surtout par la grâce voltigeante de [s]a jolie petite Colette. » Deux versions antinomiques, certes, mais qui recèlent chacune une part de vérité. Gabrielle, pour sa part, est séduite par l'esprit de cette grande figure parisienne qui lui inspire en outre une « curiosité sensuelle », comme elle l'écrira dans Mes apprentissages . Ainsi donc, Henry Gauthier-Villars épousait Sidonie Gabrielle Colette à Châtillon-Coligny, le 15 mai 1893. La famille Gauthier-Villars ne fit pas le déplacement, mais tout le village assista à la fête. Évoquant ce mariage, bien des années plus tard dans Noces , Colette se souviendra de la simplicité de la cérémonie : « Ç'avait été un petit mariage bien modeste que le mien […]. Point de messe, une simple bénédiction l'après-midi à quatre heures. » Simplicité d'une cérémonie qui scellait pourtant une union qui aura une incidence capitale sur la littérature française du XX e siècle.

Printemps 1893. Monsieur et Madame Gauthier-Villars emménagent à Paris. Le couple s'installe au dernier étage du 55, quai des Grands-Augustins, dans les deux chambres qui forment la garçonnière de Willy et qu'il a baptisé le « Venusberg », en hommage à Wagner. Ces deux pièces exiguës, où l'obscurité règne en maître, ne rappellent en rien la description que Sido avait donné du futur logis des époux dans sa lettre à Juliette. L'appartement qui les accueillera à partir de la fin du mois de juin au 28, rue Jacob sera à peine plus attrayant, trois pièces au troisième étage, entre deux cours. Sortie de ces contingences domestiques, la vie qui s'offre à Gabrielle est autrement plus scintillante et trépidante qu'elle ne voudra le faire croire plus tard. Le temps venu, le tableau sera noirci à souhait pour imposer au public les contours d'une réalité qu'elle aura habilement déformée pour discréditer Willy. Celui-ci, il est vrai, est loin de composer un modèle de fidélité. Dès les premiers mois de son mariage, Gabrielle découvre que son mari la trompe. Deux lettres anonymes vont ruiner son innocence. La première date de 1893 et l'informe que Louise Willy, une mime qui connaît un certain succès au music-hall, a de bonnes raisons de s'appeler ainsi. La seconde lettre qui lui parvient au début de 1894 est encore plus précise que la précédente, elle donne un nom, une rue et même l'heure du rendez-vous. Colette se rend donc à l'adresse indiquée et découvre Willy en compagnie d'une dénommée Charlotte Kinceler. Le choc qui s'ensuivra sera d'une extrême âpreté. Colette tombe malade, une étrange langueur s'abat sur elle. Maladie psychosomatique dirions-nous aujourd'hui. Pendant deux mois, la jeune femme semble hésiter entre la vie et la mort. Impuissant, le médecin qui la soigne appelle Sido au secours. Lorsqu'elle ira mieux, Willy l'emmènera passer sa convalescence à Belle-Île-en-Mer, de juin au début de septembre 1894. L'océan, qu'elle découvre pour la première fois, achève de la revivifier. Le temps est venu pour Gabrielle de « ne plus mourir pour personne, ni de personne », et de faire sa véritable entrée dans le monde.

Obéissant probablement aux suggestions de son époux, Gabrielle avait abandonné son prénom au profit de celui de Colette et y avait accolé celui de Willy. Jeune, jolie, piquante, Colette Willy ne tarde pas à briller dans le monde coloré des salons parisiens où l'introduit son époux. Dès l'annonce de son mariage avec Willy, Colette était attendue comme une curiosité. Et de fait, elle avait de quoi surprendre ses contemporains : son accent bourguignon, ses longues tresses, ses yeux pers, et surtout son esprit alerte et caustique apportent autant de fraîcheur et de nouveauté dans le monde bien policé des salons mondains. Sous l'œil amusé de Monsieur Willy, la jeune femme va charmer une bonne partie du Tout-Paris de la Belle Époque. Personnage très en vue, Willy a ses entrées dans tous les lieux où s'exerce la mondanité, y compris les plus sélectifs. Le couple est de tous les salons, de toutes les coteries : Madame de Saint-Marceaux, Madame de Saint-Victor, Madame de Pierrebourg, la princesse Armande de Polignac, Judith Gauthier (la fille de Théophile), les Vallette, entre autres, leur ouvrent leurs portes. Aux mercredis de Madame Arman de Caillavet, l'égérie d'Anatole France, elle fait la rencontre du jeune Marcel Proust dont l'extrême raffinement l'exaspère. L'épisode malheureux sera transposé dans Claudine en ménage  : « Un mercredi, je fus traquée, poliment, par un jeune et joli garçon des lettres. Mon petit complimenteur, excité par ses propres évocations, ne me lâchait plus. Il faillit me gâter un cassoulet divin, spécialité de la maison, servi dans de petites marmites cerclées d'argent. Il me contemplait de ses yeux caressants, à longs cils, et murmurait, pour nous deux : ‘‘Ah ! c'est la rêverie de Narcisse enfant, que la vôtre, c'est son âme emplie de volupté et d'amertume… – Monsieur, lui dis-je fermement, vous divaguez. Je n'ai l'âme pleine que de haricots rouges et de petits lardons fumés.'' Il se tut, foudroyé. » Récit pittoresque où perce toute la verve endiablée de la débutante. Ce n'est que plus tard, à la veille de la Première Guerre mondiale, que Colette découvrira le talent de l'auteur de À la recherche du temps perdu . Pour l'heure, le jeune Proust n'imagine sans doute pas l'œuvre par laquelle, une dizaine d'années plus tard, il allait immortaliser l'image chatoyante de toute cette société.

La vie mondaine se poursuit donc pour Monsieur et Madame Willy, non sans quelques heurts. En 1897, leur présence au salon de Madame Arman n'est plus souhaitée. On chuchote que Willy aurait manifesté une trop grande ardeur vis-à-vis de Jeanne Pouquet, la belle-fille de Mme Arman. Indignée, cette dernière aurait alors tout révélé à Colette. D'autres voient dans cette brouille les conséquences de cette Affaire qui, en ces dernières années du XIX e siècle, agite l'opinion publique, divise les familles et sème le trouble dans les salons. En 1894, le capitaine Dreyfus avait été condamné pour haute trahison, puis dégradé publiquement l'année suivante. En cette année 1897, le débat qui oppose dreyfusards et antidreyfusards fait rage. Willy se range dans ce dernier clan, alors que Mme Arman, née Lippmann, et Anatole France soutiennent vivement la cause du capitaine. Toujours est-il que Monsieur et Madame Willy se voient signifier leur exclusion de l'avenue Hoche. Selon un procédé qui lui est cher, Willy va régler ses comptes par romans interposés, et faire de Madame Arman « l'insupportable mère Moupet des Tares, Philaminte sur le retour, Égérie pour académiciens fourbus, tenancière d'un des plus redoutables salons-parloirs où s'élabore la libre-pensée officielle » ( Suzette veut me lâcher , 1905). Colette pour sa part conserva son estime pour Madame Arman et n'oubliera jamais de quelle tendre attention elle l'avait entourée au moment de sa dépression.

Autre salon, celui de la princesse Armande de Polignac qui avait composé la musique de La Petite Sirène sur un livret de Willy. Là, poètes et musiciens se retrouvent pour disserter à loisir de leur art. Colette se trouvait parfaitement à son aise dans les cercles musicaux, et bien souvent elle étonnera son entourage par ses dons de musicienne, comme en témoigneront Liane de Pougy ou Germaine Beaumont. Au cours d'une soirée musicale donnée chez Ernest Chausson, alors que le violoniste Eugène Ysaye interprète des morceaux de Bach, le poète Albert Samain est saisi par la profondeur d'écoute de la jeune femme, c'est « la seule qui écoute avec son âme. » Albert Samain tombe littéralement sous son charme. Les Gauthier-Villars affectionnent particulièrement ces soirées musicales. C'est au cours d'une de ces soirées données dans le salon de Madame de Saint-Marceaux que Colette rencontre Claude Debussy, « le grand maître de la musique française », dit-elle. Madame de Saint-Marceaux au reste n'apprécie guère Colette qu'elle qualifie de « femme de génie et de vice. » Ce qui n'empêcha pas son époux, le sculpteur René de Saint-Marceaux, de réaliser d'après Colette un plâtre la représentant en faune. Les Willy côtoient également le monde coloré qui se retrouve dans le salon d'Alfred Vallette et de sa femme Rachilde. C'est ainsi que le couple fait la connaissance d'Alfred Jarry. Monsieur et Madame Gauthier-Villars ont également leur jour de réception. Le dimanche, ils reçoivent dans leur nouvel appartement du 177 bis rue de Courcelles : « Une vraie ménagerie. Des gens invraisemblables à côté de ‘‘noms illustres''. […] La poignée de mains échangée entre Léon Daudet et Jean Lorrain était un spectacle qui valait la peine d'être vu », se souviendra Henri Albert.