W 1889 roku Kolej Władykaukaska zamówiła w Kołomnie skonstruowanie nowego czteroosiowego parowozu z dwucylindrowym silnikiem sprzężonym (compound). Projekt wstępny sporządził inżynier służby ruchu Kolei Władykaukaskiej, Polak Wacław Łopuszyński, a rysunki robocze opracowali konstruktorzy w Kołomnie. Za wzór dla nowego parowozu (fabryczny typ 39) został wzięty typ 31, z którego bez większych zmian zaadaptowano kocioł parowy, podwyższając jednak ciśnienie robocze z 9 do 11 kg/cm². Pewne zmiany wprowadzono w podwoziu, zachowując średnicę kół 1200 mm. Silnik sprzężony miał średnice cylindrów 500 i 710 mm. Oprócz tego, zamiast mechanizmu parorozdzielczego (rozrządu) Allana zastosowano łatwiejszy w obsłudze i remontach rozrząd JoyaRakow, op.cit., s.140-141.
thumb|Parowóz typu 39 Zakładów Kołomienskich (CzK / OdK) W 1890 zbudowano dla Kolei Władykaukaskiej 10 parowozów typu 39, po czym w latach 1891−1892 zbudowano dalsze 40 parowozów nieco ulepszonego typu 40 (m.in. powierzchnia ogrzewalna kotła zmniejszona ze 174,60 do 154 m² z powodu skrócenia płomieniówek i zmniejszenia ich liczby, zmieniona konstrukcja budki i zmniejszona masa z 52,5 do 50 t oraz maksymalne obciążenie osi z 13,5 t do 12,5 t). Parowozy obu typów miały czteroosiowe tendry z zapasem wody 19,3 m³.