We report two cases of patients with hepatocellular carcinoma (HCC) that developed in cryptogenic cirrhosis suggestive of nonalcoholic steatohepatitis (NASH) as background liver disease. Case 1 was a 68-year-old woman, and case 2 was a 46-year-old man. They were admitted to our department for evaluation and treatment of HCC. The causes of the underlying liver disease were not determined from blood tests. However, histological analysis of non-tumor tissues of the liver revealed cirrhosis with few fat droplets. Both patients had undergone liver biopsy 26 years before the treatment of HCC. Histological review of the biopsy specimens revealed NASH (case 1) and fatty liver (case 2), respectively. It was suggested that these cases progressed from NASH and fatty liver, respectively, to NASH-related cirrhosis (so called burned-out NASH), eventually, developing HCC. These findings suggest that substantial number of burned-out NASH cases may be included in those with cryptogenic cirrhosis. These two patients are indicative cases that may reveal the long-term natural course of fatty liver and NASH.