Introduction. Acute-on-chronic liver failure (ACLF) is an acute liver decompensation in cirrhotic patients, which leads to organ failures and high short-term mortality. The treatment is based on the management of complications and, in severe cases, liver transplantation. Since specific treatment is unavailable, we aimed to evaluate the safety and initial efficacy of bone marrow mesenchymal stem cells (BM-MSC) in patients with ACLF Grades 2 and 3, a population excluded from previous clinical trials. Methods. This is a randomized placebo-controlled phase I-II single center study, which enrolled 9 cirrhotic patients from 2018 to 2020, regardless of the etiology. The control group (n = 5) was treated with standard medical therapy (SMT) and placebo infusion of saline. The intervention group (n = 4) received SMT plus 5 infusions of 1 × 106 cells/kg of BM-MSC for 3 weeks. Both groups were monitored for 90 days. A Chi-square test was used for qualitative variables, and the t-test and Mann–Whitney U test for quantitative variables. The Kaplan–Meier estimator was used to build survival curves. In this study, we followed the intention-to-treat analysis, with a significance of 5%. Results. Nine patients with a mean Child–Pugh (CP) of 12.3, MELD of 38.4, and CLIF-C score of 50.7 were recruited. Hepatitis C and alcohol were the main etiologies. The average infusion per patient was 2.9 and only 3 patients (2 in control and 1 in the BM-MSC group) received all the protocol infusions. There were no infusion-related side effects, although one patient in the intervention group presented hypernatremia and a gastric ulcer, after the third and fifth infusions, respectively. The survival rate after 90 days was 20% (1/5) for placebo versus 25% (1/4) for the BM-MSC. The patient who completed the entire MSC protocol showed a significant improvement in CP (C-14 to B-9), MELD (32 to 22), and ACLF (grade 3 to 0). Conclusion. BM-MSC infusion is safe and feasible in patients with ACLF Grades 2 and 3.