Der Sohn eines Bergbauingenieurs studierte in Wien Rechtswissenschaft (ohne Abschluss) und betätigte sich früh als Journalist. Leuthner schloss sich zunächst den Liberalen an, befasste sich aber intensiv mit den Lehren von Marx und Lassalle. Als er am 14. März 1893 in den Sofiensälen eine Rede zum 10. Todestag von Karl Marx hielt, wurde er von einem Ehrenrat der Armee seiner Charge als Reserveleutnant der Kavallerie für "verlustig" erklärt und zum gewöhnlichen Infanteristen degradiert. Vermutlich brachte ihn dieses Erlebnis in engeren Kontakt zur Sozialdemokratie.

Nachdem die Arbeiter-Zeitung ab 1. Januar 1895 täglich erschien, wurde Karl Leuthner Redakteur des Blattes für Außen- und Militärpolitik. Leuthner war nicht nur ein hervorragender Journalist, sondern auch ein blendender Redner. Er sprach in unzähligen Versammlungen und war wegen seines enormen Wissens auch eine dominante Persönlichkeit im Bildungswesen der Partei.

Von 1911 bis 1918 war Karl Leuthner, der dem rechten Flügel der Sozialdemokratischen Arbeiterpartei zugerechnet wurde, Mitglied des Reichsrates, und ab 1918 Mitglied der Provisorischen und der Konstituierenden Nationalversammlung sowie von 1920 bis 1934 Abgeordneter zum Nationalrat, wo er sich v.a. mit Fragen der Außenpolitik befasste. Zudem war Leuthner einer der bedeutendsten Vorkämpfer des Freidenkertums in Österreich. Nach 1934 zog sich Leuthner völlig ins Privatleben zurück.

Die in den Jahren 1931/32 nach Plänen von Georg Rupprecht errichtete Wohnhausanlage der Gemeinde Wien, 6., Mollardgasse 89 / Linke Wienzeile 182, wurde Leuthnerhof benannt.

Werk: Russischer Volksimperialismus, 1915; Religion und Sozialdemokratie, 1923; Frau, Christentum und Sozialismus, 1925.