The management of degenerative lumbosacral stenosis (DLSS) in dogs usually requires aggressive, costly surgical treatments that may themselves present complications, while do not fully resolve the symptoms of the disease. In this study, the dog diagnosed with severe DLSS, with hind limb paresis, was treated using a new and least invasive treatment. Cultured autologous adipose tissue-derived mesenchymal stem cells (AT-MSCs) were injected bilaterally at the level of L7-S1, in the vicinity of the external aperture of the intervertebral foramen of DLSS patient. In the previously described treatments of spontaneous intervertebral disc degeneration in dogs, intradiscal injections of MSCs did not lead to positive effects. Here, we report a marked improvement in clinical outcome measures related to the ability of a dog to walk and trot, which were expressed by a numeric rating scale based on a veterinary assessment questionnaire. The improved status persisted throughout the observed time course of 4.5 years after the AT-MSC transplantation. To the best of our knowledge, this is the first case of successful therapy, with long-term positive effect, of spontaneously occurring canine DLSS using presented treatment that, we believe, represents a contribution to current knowledge in this field and may shape both animal and human DLSS treatment options.