K 1. dubnu 1959 byla založena rejdařská společnost Československá námořní plavba (ČNP) se statutem mezinárodní akciové společnosti (zvolena v té době vyjímečná forma právnické osoby pro podnik). Tím došlo k historickému mezníku ve vývoji naší námořní plavby – na světových mořích a oceánech se objevuje nová vlajka: modrý obdélník v jehož geometrickém středu je bílý kruh v němž je vepsána červená hvězda s vrcholem vzhůru (autor kpt.Hakl).. Do společnosti bylo vloženo dosavadních 5 lodí, z nichž 4 patřily zahraničnímu partnerovi ČLR.

Ústředním ředitelem byl jmenován František Navrátil. Sídlem podniku se staly najaté prostory v budově na rohu ulice Na příkopě a Na Můstku, odkud se v roce 1970 ČNP přestěhovala a kde byl po výstavbě stanice metra trasy A postaven  nový objekt, kam již se podnik nevrátil.

Podnik se po založení potýkal s nedostatkem nových pracovníků, z nichž řada neměla žádné zkušenosti s námořním obchodem ani provozem (v ústředí byla část zejména vedoucích funkcí obsazena duplicitně čínskými pracovníky, rovněž na lodích byly posádky smíšené). Nevyhnuly se mu ani  finančními problémy  (přidělené finanční prostředky nestačily na financování  předzásobení lodí a dovybavení nově vzniklého ústředí), což bylo vyřešeno krátkodobým úvěrem a později zcela nahrazeno vlastními příjmy z fakturace dopravného..

Bylo nutno vyřešit řadu problémů s evidencí, zejména účetní, která byla vedena v cenách zahraničního obchodu (tím docílena základní baze srovnatelnosti přímých nákladů na provoz lodí s tržbami za námořní dopravné). Tržby byly vyjádřeny ve světových cenách, část nákladů však byla placena ve vnitřních cenách (mzdy, dodávky z ČSR, provoz ústředí apod.) a část v tzv.neobchodních (koeficientovaných) platech (náklady v přístavech ZST), které byly vyrovnávány zúčtováním rozdílů s nadřízeným orgánem MZO.

Provoz byl založen na vzájemné výměně čs. a čínského zboží doplněné přikládkami v nácestných přístavech, v Evropě operovaly lodě převážně v bulharské Varně a rumunské Konstanci, při nakládce i vykládce s dlouhými postoji, což se týkalo i čínských přístavů. Při postojích v Evropě čerpaly čs.posádky dovolenou a provádělo se i jejich střídání a zásobování lodí potravinami, materiálem a náhradními díly.

Z celkového počtu pracovníků tvořily lodě 80%, ústředí 20%.V roce 1959 bylo na  ústředí 11 Číňanů , na lodích pak 125 cizích příslušníků, převážně opět Číňanů.

Do provozu uvedeny dvě další čínské lodě: Ostrava (motorový tanker postavený v jugoslávské Pule postavený ve spolupráci s čínským rejdařem, dosud jediná loď pro přepravu tekutého substrátu, moderně vybavená včetně klimatizace, palubní mechanismy byly z bezpečnostních důvodů poháněny párou) a zařazena loď Orava I. (původně loď Chipolbroku Žeromski, sesterská loď Dukly, postavená v roce 1957 ve Warnemünde v NDR). Chipolbroke byl společný čínsko-polský podnik pro námořní dopravu, obdoba ČNP.

Do provozu uvedena (do výsledku se však nepromítla) rovněž druhá čs.loď Kladno (považována za naši nejspolehlivější a nejefektivnější loď, s velice kvalitním hlavním motorem a ostatním zařízením, bez větších nároků na údržbu a s minimální poruchovostí, postavená téhož roku v loděnicích Hitachi v japonské Osace).

Od začátku provozu lodě překročily první stovku ukončených cest a první milion přepravených tun i ujetých mil.

Zatímco přepravní výkony se přírůstkem nových lodí výrazně zvýšily, zisk se dále zhoršil  (lodě Republika I. a Dukla skončily ztrátově) a přínos se zvýšil pouze v důsledku odpisů), pokles tím zaznamenala i návratnost.

Od začátku provozu lodí byla dovršena stá cesta, miliontá přepravená tuna a miliontá ujetá míle.

Všechny lodě pro suchý náklad i tanker byly provozovány v DV relaci. Tanker Ostrava uskutečnil 3 cesty s nakládkou v Konstantzi a vykládkou ve Whampoa a Tsamkongu. Na zpáteční cestě do Evropy přepravil náklad z Abadanu do Lisabonu.