A 2-year-old child with fibrodysplasia ossificans progressiva underwent a muscle biopsy of a very early lesion, and had findings that showed the earliest stage ever seen in the histopathology of fibrodysplasia ossificans progressiva. This very early stage consisted of intense perivascular lymphocytic infiltration into normal appearing skeletal muscle. A nearly identical histopathologic sequence was noted in a cat with phenotypic features similar to those of fibrodysplasia ossificans progressiva in humans. These new findings represent the earliest documented changes that have ever been noted in fibrodysplasia ossificans progressiva, and provide further histopathologic support for the recent discovery that lymphocytes may play a role in the pathogenesis of heterotopic ossification in fibrodysplasia ossificans progressiva.