We present here the first report of disseminated skin Mycobacterium infections in two liver transplant recipients, in which hsp65 gene sequencing was used for rapid species identification. Both patients had hepatitis B virus-related cirrhosis and diabetes mellitus and presented with progressive generalized, nodular skin lesions. In one patient, a 50-year-old woman who had frequent contact with marine fish, an acid-fast bacillus was isolated from skin biopsy tissue after 2 months of culture. While awaiting phenotypic identification results, hsp65 gene sequencing showed that it was most closely related to that of Mycobacterium marinum with 100% nucleotide identity. The patient was treated with oral rifampin, ethambutol, and moxifloxacin. In the other patient, a 59-year-old woman, direct PCR for Mycobacterium using hsp65 gene from skin biopsy tissue was positive, with the sequence most closely related to that of M. haemophilum with 100% nucleotide identity. Based on PCR results, the patient was treated with clarithromycin, ethambutol, moxifloxacin, and amikacin. A strain of M. haemophilum was only isolated after 3 months. Skin lesions of both patients resolved after 1 year of antimycobacterial therapy. Nontuberculous Mycobacterium infections should be considered in liver transplant recipients presenting with chronic, nodular skin lesions. This report highlights the crucial role of hsp65 gene PCR and sequencing on both cultured isolates and direct clinical specimens for rapid diagnosis of slow-growing Mycobacterium infection.