Fetal rhabdomyoma is not generally considered part of nevoid basal cell carcinoma syndrome. However, a review of the literature revealed five patients with this syndrome who also had fetal rhabdomyomas in various locations. We report the first patient with nevoid basal cell carcinoma syndrome and a fetal rhabdomyoma of the tongue. We recommend that embryonal rhabdomyosarcoma be ruled out to avoid overly aggressive treatment of these patients.