O provozu na lince Praha – Moskva se začalo uvažovat již v r. 1931. Polská vláda však tehdy odvolala svůj souhlas k přeletům přes Polsko. Proto bylo navrženo směřovat linku přes Rumunsko. 16.5.1935 byla uzavřena smlouva mezi ČSA a Aeroflotem.

Linka měla šest etap:
Praha (Kbely) – Užhorod – Kluž – Jasy – Kyjev – Brjansk – Moskva (Tušino).

První let z Prahy do Moskvy uskutečnil Airspeed AS-6 Envoy ČSA už 9.9. 1935. Opačným směrem letělo letadlo Antonov ANT-9 Aeroflotu 30.10.1935. Následovaly technické lety, přičemž 1.2.1936 byla údajně přepravena pošta. 
Pravidelný provoz na lince byl zahájen 1.9.1936 letounem ANT-9 ve směru Moskva –Praha a z Prahy do Moskvy odletěl letoun AS-6 (pilot K. Brabenec) následující den. Provoz na lince trval do r. 1938, kdy už na jaře nebyl zahájen vzhledem ke zhoršující se mezinárodní situaci. Jednalo se o nejdelší linku ČSA.

Poválečný pravidelný provoz obnovil Aeroflot letadly Lisunov Li-2 dne 4.8.1945. ČSA v té době na lince nelétaly. Vlastní provoz na lince zahájily až 18.4.1955 a létaly se stroji Il-12 a Il-14 (Avia Av-14). Aeroflot používal především stroje Li-2, Il-12 a DC-3. První proudový Tupolev Tu-104 přiletěl z Moskvy do Prahy 15.6.1956 (technický let) a pravidelně začaly Tu-104 Aeroflotu obsluhovat linku od 12.10.1956.
ČSA vstoupily jako jedna z prvních leteckých společností světa do epochy proudových letadel, tím že jako první úspěšně zařadily od 9.12.1957 do pravidelného mezinárodního provozu na lince Praha-Moskva letadla Tupolev Tu-104A.