Die Gemeinden Baukau, Herne und Recklinghausen schlossen am 4. Februar 1896 einen Vertrag, auf der Strecke zwischen ihren Orten eine Straßenbahn zu bauen und gründeten zu diesem Zweck die Straßenbahn Herne–Baukau–Recklinghausen.

Auf der Strecke zwischen den Orten wurde seit dem Jahr 1888 eine Pferdeomnibuslinie betrieben, welche viermal am Tag diese Strecke befuhr. Am 26. Februar 1898 wurde die meterspurige Straßenbahn zwischen Recklinghausen Viehtor und Herne Bahnhof in Betrieb genommen. Die Strecke hatte, nachdem am 1. November 1903 eine Verlängerung bis Recklinghausen Markt und am 3. Februar 1905 eine Verlängerung bis Recklinghausen Hauptbahnhof in Betrieb gingen, eine Länge von 9,1 Kilometern. Die Bahn beförderte auf dieser Strecke zwischen 2 und 3 Millionen Fahrgäste jährlich und war somit eine der Leistungsfähigsten im gesamten Ruhrgebiet.

Als 1908 die Gemeinde Baukau zur Stadt Herne eingemeindet wurde verschwand sie auch aus dem Firmennamen. Somit hieß das Unternehmen ab 1908 nur noch Straßenbahn Herne–Recklinghausen. In den Jahren zwischen 1908 und 1928 hat die Bahn insgesamt fast 400 m Strecke an die Bahnen der Stadt Recklinghausen, bzw. ihre Nachfolgerin, die Vestische Kleinbahn GmbH abgegeben. Am 2. Juni 1923 übernahm die Vestische Kleinbahn GmbH die Betriebsführung. Das Unternehmen blieb aber eigenständig.

In den 20er Jahren wurde die Linie zweigleisig ausgebaut und ein 10-Minuten Takt auf der Strecke eingeführt. Zum Teil verliefen die Gleise schon auf einem eigenen Bahnkörper. Am 28. Oktober 1939 kam das Ende der Eigenständigkeit und die Bahn ging in den Besitz der Vestischen Kleinbahn GmbH über.