Se stavbou parníku Bohemia se začalo v karlínské loděnici v roce 1840, na vodu byl spuštěn 1. května 1841 v 15.30 h. Zkušební plavby parníku, který byl přes 37 metrů dlouhý, uvezl 140 pasažérů a jako pohon využíval parní dvouválec o výkonu 23 kW, proběhly o dva týdny později mezi Libeňským jezem a Rohanským ostrovem za účasti mnoha novinářů i veřejných činitelů.
Bohemia se poté 23. května 1841 vydala na první plavbu do Mělníka a dále do Obříství, které bylo vhodným mezipřistáním pro plavbu do Drážďan. Do saské metropole loď dorazila 26. května 1841 a hned slavila velký úspěch. Německé parníky měly totiž větší ponor a pro nízký stav vody nemohly v té době vůbec vyplout.
Andrews s Rustonem se brzy rozhodli, že výchozím bodem svých plaveb do Drážďan zvolí až Obříství, protože se ukázalo, že Vltava není pro pravidelný provoz lodí způsobilá. Cestující z Prahy museli tedy část trasy urazit bryčkou nebo dostavníkem, paroplavba se ale i přesto stala oblíbenou a podnikání se velmi dařilo. Později si Andrews pronajal patro zámku v Obříství a zřídil zde 22 lůžkových pokojů a restauraci.
Parník Bohemia vyrážel z přístavu v Obříství dvakrát týdně v sedm hodin ráno: plul 170 kilometrů z Obříství do Drážďan necelých 12 hodin a zpět 17 hodin. Provoz byl po čase rozšířen a v červnu 1846 se začal používat i druhý parník Germania.
