We assessed the safety and efficacy of sorafenib with cryotherapy (cryoRx) in advanced hepatocellular carcinoma (HCC). One hundred four HCC patients were enrolled, who met the following criteria: (i) Barcelona Clinic Liver Cancer stage C; (ii) HCC without distant metastasis; (iii) the presence of portal vein thrombosis (PVT); (iv) Child-Pugh class A or B; and (v) life expectancy of at least 12 weeks. The patients were randomly divided into sorafenib-cryoRx and sorafenib (control) groups. Primary endpoint was time to progression (TTP); secondary endpoints included overall survival (OS) and tolerability. Microvessel density (MVD) was assessed by CD34-immunostaining. After a median 10.5 (4-26) months follow-up, the data showed that median TTP was 9.5 (8.4-13.5) months in combinatorial therapy group vs. 5.3 (3.8-6.9) months in sorafenib group (P = 0.02). The median OS was 12.5 (95 % CI 10.6-16.4) months in combination therapy group vs. 8.6 (7.3-10.4) months in sorafenib group (P = 0.01). Low MVD patients in combination therapy exhibited significantly longer median TTP and OS than controls. High MVD was predictive of poor responses to sorafenib. CryoRx did not increase frequency/degree of sorafenib-related adverse events. Therefore, it was concluded that the addition of cryoRx significantly improved clinical outcomes of Sorafenib therapy in advanced HCC with acceptable tolerance and similar safety profiles as previously reported.