Direkte Vorgängerin der Arbeiter-Zeitung aber war die 1886 gegründete und von Victor Adler herausgegebenen Gleichheit, deren Redaktion und Verwaltung sich in der Gumpendorfer Straße 73 befand. Nachdem das Blatt 1889 verboten wurde,  gründete Adler am gleichen Ort die Arbeiter-Zeitung, die erstmals am 12. Juli 1889 erschien, zunächst zweimal im Monat, ab 18. Oktober 1889 wöchentlich, und ab 1. Januar 1895 täglich – bis zu ihrem Verbot am 12. Februar 1934.
Die Druckerei, in der die Arbeiter-Zeitung ab der ersten Nummer bis zum Februar 1893 hergestellt wurde, befand sich anstelle des heutigen, 1910 neu errichteten Hauses Alserstraße 32 im 9. Bezirk. Von 1893 bis zum 24. April 1900 wurde die Zeitung in der Universitätsstraße 6-8 gedruckt; die Redaktion und das Expedit befanden sich im Haus Schwarzspanierstraße 10 / Ferstelgasse 6. Die Zeitung hielt damals bei einer Auflage von etwa 24.000 Stück.

Nach dem Zweiten Weltkrieg erschien die Arbeiter-Zeitung ab dem 5. August 1945 wieder als Parteizeitung der SPÖ und war bis 1955 mit einer Auflage von 245.000 Stück die größte Zeitung Österreichs.

Während der Besatzungszeit war die Arbeiter-Zeitung nicht nur
die verlässliche Chronistin des politischen, kulturellen und wirtschaftlichen Wiederaufbaus – sie wurde als die Zeitung, die sich was traut berühmt, weil sie sich besonders für die Rechte der Österreicher gegenüber den Besatzungsmächten stark machte.

Während der großen Streikbewegung des Jahres 1950 bildete ihre Berichterstattung eine Speerspitze zur Unterstützung von Exekutive und ÖGB bei der Niederschlagung des "kommunistischen Putschversuchs".

Ende der fünfziger Jahre schlitterte die Arbeiter-Zeitung durch das Aufkommen der Boulevardpresse in ihre erste Krise.

1961 kam es deshalb auch zu einem Wechsel an der Spitze: Franz Kreuzer sollte als neuer Chefredakteur das bereits etwas verstaubt wirkende Blatt modernisieren. Sichtbarstes äußeres Zeichen war die Veränderung des Titelkopfes – aus der "Arbeiter-Zeitung" wurde die "AZ".

Während der Ära Bruno Kreisky trat die Arbeiter-Zeitung für eine Öffnung und Erneuerung der Partei ein – und öffnete sich selbst:
So etwa erregte das Engagement der "roten Gräfin" Barbara Coudenhove-Kalergi für das außenpolitische Ressort einiges Aufsehen. Dennoch geriet das Blatt gerade in den Zeiten der größten SPÖ-Erfolge immer mehr in eine ökonomische Schieflage. Ende der siebziger Jahre wurde die AZ deswegen in eine neue Eigentümerstruktur – aber weiter in Parteibesitz – übergeführt und Albrecht K. Konecny als Herausgeber des Blattes berufen.