I slutningen af 1860´erne var de jydske hovedbaner ved at være færdigbygget, og de byer der var blevet forbigået i første omgang mente, at nu var turen kommet til dem. En af byerne var Grenå med kun omkring 2.000 indbyggere men til gengæld med en havn, der næsten altid var isfri grundet beliggenheden ud til Kattegat. Den nærmeste større by på den østjydske længdebane var Randers, hvis havn i bunden af Randers Fjord ofte frøs til, og det var derfor oplagt at føre banen hertil.
Staten var ikke interesseret i at bygge flere baner men ville gerne yde et tilskud såfremt private ville påtage sig opgaven, og i maj 1873 vedtog Rigsdagen at yde tilskud til tre private baner: Silkeborg-Herning (SHB), Odense-Svendborg (SFJ) og Randers-Grenå (ØJJ). I Randers påbegyndtes aktietegningen og da koncession for banen var blevet udstedt i juni 1874, gik anlægsarbejdet i gang.
I Århus var man blevet nervøs for, at hele Djursland, der var byens nordlige opland, skulle overgå til Randers med deraf følgende nedgang i handelen, og man foreslog derfor en bane fra Århus til et punkt på Randers-Grenå banen. I maj 1875 vedtog Rigsdagen et tillægslov omhandlende en bane fra Århus til Ryomgård, og de to baneselskaber enedes om et driftsfællesskab i foreløbig 5 år. Indtægter og udgifter skulle dog deles ud fra et fordelingstal baseret på banernes længde: Randers-Grenå 63% og Århus-Ryomgård 37%.
Der gik næsten to år før Randers-Grenå banen var færdig, bl.a. fordi hovedentreprenøren og finansmanden Gedalia gik konkurs under byggeriet, og fordi der ved Pindstrup var store moseområder, der skulle fyldes op med jord. Randers-Grenå banen blev indviet den 24. august 1876 med indvielsestog, taler og festmiddag om aftenen, og to dage senere påbegyndte banen den ordinære drift med to tog dagligt i hver retning.
Østjyske Jernbane var 64 km lang og havde sit udgangspunkt på statsbanestationen i Randers. Herefter fulgte Strømmen station, Volkmølle billetsalgssted, Uggelhuse station, Floes billetsalgssted, Allingåbro station, Auning station, Pindstrup station, Ryomgård station, Kolind station, Hallendrup billetsalgssted, Trustrup station, Ålsø billetsalgssted og Grenå station med tilhørende havnebane. Til at varetage driften indkøbtes 4 små damplokomotiver ØJJ 1-4 fra Hanomag, der var identiske med de af JFJ indkøbte litra L i 1875. Banens 78 vogne blev leveret af Scandia i Randers, der på det tidspunkt hed Randers Jernbanevogn Fabrik.

Banen mellem Århus og Ryomgård blev indviet uden den helt store festivitas den 30. november 1877, og normal drift påbegyndtes dagen efter. Selv med de sædvanlige problemer i form af bundløse moser m.v. var det lykkedes at færdiggøre banen 1 år tidligere end angivet i koncessionen.
Århus-Ryomgård banen etablerede egen lokalstation i Århus kaldes Århus Østbanegård, og herefter fulgte Risskov holdeplads, Lystrup station, Hjortshøj station, Skødstrup station, Løgten station, Hornslet station, Mørke station, Thorsager station og Ryomgård station på Randers-Grenå banen i alt 38,2 kilometer.
Driftsmateriellet blev forøget med tre damplokomotiver ØJJ 5-7, der var identiske med de tidligere leverede ØJJ 1-4. Scandia i Randers leverede 44 person- og godsvogne af forskellige typer, der dog var magen til de typer, der var leveret året før.

ØJJ havde svært ved at tjene penge; i 1878 og 1879 var overskuddet blot 1% af investeringen, og der var ikke engang penge til at betale renter med. Staten overtog af flere omgange banens lån, og der var kun en realistisk løsning - nemlig at staten overtog banen. Den 1. oktober 1881 overgik begge baner, personale samt rullende materiel til de Jydsk-Fynske Statsbaner og ØJJ var dermed et afsluttet kapitel på Djursland.

- ØJJ damplokomotiver
- ØJJ person- og rejsegodsvogne
- ØJJ godsvogne

Læs mere om Østjyske Jernbane her:
Wikipedia