Cölestine Truxa, geb. Öppinger, übernimmt 1886 die Herausgabe der „Verkehrs-Zeitung“ von ihrem Ehemann Leo Truxa, nachdem dieser plötzlich und unter unklaren Umständen verstorben war.

Sie ist langjähriges Mitglied und in den Jahren 1889 bis 1890 stellvertretendes Ausschussmitglied im Verein der Schriftstellerinnen und Künstlerinnen, Wien. Außerdem ist sie eine der Schriftführerinnen der Auskunftsstelle für Wohlfahrtseinrichtungen in Wien.

Durch die Anwerbung von Aurelie Obermayer beginnt Cölestine Truxa 1903 ihre Mitarbeit in der Österreichischen Liga zur Bekämpfung des Mädchenhandels, die 1902 von einigen Männern und Frauen – darunter auch Marianne Hainisch – gegründet worden war. Im November 1903 übernimmt Cölestine Truxa zunächst die Führung der Vereinsgeschäfte. 1904 wird sie zur Generalsekretärin gewählt und hat diesen Posten bis 1914 inne. In dieser Zeit gewinnt sie finanzkräftige und einflussreiche Persönlichkeiten als Vizepräsidenten und baut den Verein zu einer weitvernetzten Organisation innerhalb der Habsburgermonarchie aus. In diesem Kontext vernetzt sie sich auch mit Bertha Pappenheim, die zu dieser Zeit den jüdischen Verein Weibliche Fürsorge in Frankfurt am Main leitet. In ihrer Privatwohnung (Köstlergasse 5, im 6. Wiener Gemeindebezirk) richtet Cölestine Truxa eine Fürsorgestelle ein, von der aus sie jungen Mädchen und Frauen in prekären Lebenslagen Ausbildungs- und Arbeitsstellen vermittelt. Durch die Arbeit der Liga finden unzählige Frauen Unterstützung, etwa in einer eigens eingerichteten Schutzstation in Wien.

Von 1887 bis 1896 ist sie die Vermieterin und Hauswirtin von Johannes Brahms. Auf diese Weise kann sie einige zerrissene Stücke des Komponisten aus dem Papierkorb retten und für die Nachwelt aufbewahren. Sie betreut Brahms in seinen letzten Lebensstunden.