Le Café de la Gare est créé juste après les événements de mai 68 par un groupe d’amis qui ont restauré une vieille fabrique de ventilateurs passage d'Odessa (dit aussi « passage du Départ »), proche de la gare de Paris-Montparnasse à Paris dans le 14e arrondissement.
Romain Bouteille, qui se présente lui-même comme « un libertaire consciencieux », relate cette période : « Nous, on en avait un peu marre de tout ça, des cabarets où le bonhomme était tout seul, où il n’y avait pas de troupe. C’est pour ça qu’en 1968 il devenait important pour Coluche et moi de faire un théâtre qui n’avait pas existé : un théâtre avec l’interdiction d’interdire. Je croyais en l’efficacité d’un groupe déhiérarchisé, avec le partage équivalent de tout bénéfice éventuel, sans apprentissage »[1].
Sur le plan humain, Coluche considère le mode de vie de la troupe d'inconnus est basé du « copinage en concubinage ». Coluche vit avec sa petite amie Miou-Miou. Compagne de Romain Bouteille, Sotha le quitte pour épouser Patrick Dewaere, lequel séduit ensuite Miou-Miou.
Le , le Café donne son premier spectacle : un ensemble de textes burlesques signés Bouteille, Sotha, Gégé et Dewaere.
La salle est inachevée, le slogan du lieu est désormais « C'est moche, c'est sale, c'est dans le vent ».
À son ouverture, le Café de la Gare se présente comme un « café-théâtre », terme vague qui, à l'époque, se conforme surtout à une contrainte de catégorie fiscale. Cependant, on n'y boit jamais de café et il n'y a jamais eu de tables ni de chaises ; seulement des gradins pour environ 180 personnes, entourant sur trois côtés une scène d'environ 8 mètres sur 5.
Chaque soir, le public qui arrive pour voir ce théâtre de la dérision et de la farce, doit se plier à un rituel : chacun tire au sort le prix de sa place, grâce à une roue de type loterie, laquelle est actionnée par l'un des comédiens. Ainsi, les plus chanceux ne paient rien, voire récupèrent même 1 franc et les moins chanceux paient le prix d'une place de cinéma. Une fois assis sur les bancs, les spectateurs ont droit à une boisson chaude ou froide, servie par ces mêmes acteurs, ainsi qu'à un coussin qui est généralement jeté en pleine figure par ces derniers.
La légende de l'improvisation permanente, exagérée, sert de catalyseur. Les deux premiers spectacles Allume, j'étouffe... et Des boulons dans mon yaourt présentent une succession de sketches écrits par l'ensemble des acteurs.
Toutefois, ce succès inquiète Bouteille. Il cherche à imposer ses choix : pas de chef, pas de metteur en scène, l'acteur reste maître de son texte, répartition de la recette en parts égales, pas de sanctions, celui qui s'en va doit trouver un remplaçant. En 1970, à la suite de problèmes d'alcool qui le rendent exécrable voire violent, Coluche invective et va jusqu'à frapper Bouteille, alors qu'ils répètent Des boulons dans mon yaourt ; l'humoriste se voit obligé de quitter la troupe.
En 1971, le café de la Gare déménage au 41 rue du Temple dans le 4e arrondissement, dans un relais de poste du XVIIe siècle anciennement appelé l'« Auberge de l'Aigle d'Or ». Il devient alors le plus grand café-théâtre de la capitale avec une salle de 450 places.
En 1976, le Groupement des institutions sociales du spectacle impose aux directeurs de lieux comme le Café de la Gare, de régulariser leur situation pour les cotisations retraites, les congés spectacle, les ASSEDIC et le fond nationational de garantie des salaires (FNGS). Cinq lieux sont touchés par ce procès : le Café de la Gare, le Bec-Fin, le Coupe-Chou, Le Plateau et le Sélénite. Le 10 novembre 1977, le tribunal rend son verdict et les cafés-théâtres doivent se mettre en règle, ce qui est très coûteux pour la troupe[2].
En 2010, cinquante théâtres privés de Paris réunis au sein de l’Association pour le soutien du théâtre privé (ASTP) et du Syndicat national des directeurs et tourneurs du théâtre privé (SNDTP), dont fait partie le Café de la Gare, décident de se renforcer grâce à une nouvelle enseigne, symbole du modèle historique du théâtre privé : les Théâtres parisiens associés[3].
En mai 2014, Marie-Christine Descouard (présente au Café de la Gare de 1973 à 1981) publie aux éditions Le Cherche midi un livre intitulé Le Café de la Gare, quelle histoire !.
En 2018, la salle du café de la Gare et sa salle de théâtre sont le lieu de tournage de l'émission Dans la gueule du loup, produite par Jacques Cotta et l'entreprise de presse de webtélé Le Média[4].