Background: Injection of autologous adipose tissue (AT) has recently been demonstrated to be an effective and safe treatment for anal fistulas. AT mesenchymal stem cells (AT-MSCs) mediate the healing process, but the relationship between molecular characteristics of AT-MSCs of the injected AT and fistula healing has not been adequately studied. Thus we aimed to characterize the molecular and functional properties of AT-MSCs isolated from autologous AT injected as a treatment of cryptogenic high transsphincteric perianal fistulas and correlate these findings to the healing process. Methods: 27 patients (age 45 ± 2 years) diagnosed with perianal fistula were enrolled in the study and treated with autologous AT injected around the anal fistula tract. AT-MSCs were isolated for cellular and molecular analyses. The fistula healing was evaluated by MRI scanning after 6 months of treatment. AT-MSC phenotype was compared between responders and non-responders with respect to fistula healing. Results: 52% of all patients exhibited clinical healing of the fistulas as evaluated 6 months after last injection. Cultured AT-MSCs in the responder group had a lower short-term proliferation rate and higher osteoblast differentiation potential compared to non-responder AT-MSCs. On the other hand, adipocyte differentiation potential of AT-MSCs was higher in non-responder group. Interestingly, AT-MSCs of responders exhibited lower expression of inflammatory and senescence associated genes such as IL1B, NFKB, CDKN2A, TPB3,TGFB1. Conclusion: Our data suggest that cellular quality of the injected AT-MSCs including cell proliferation, differentiation capacity and secretion of proinflammatory molecules may provide a possible mechanism underlying fistula healing. Furthermore, these biomarkers may be useful to predict a positive fistula healing outcome. Trial registration: NTC04834609, Registered 6 April 2021. https://clinicaltrials.gov/ct2/show/NCT04834609.