Soft gingival tissue deficiency remains a severe problem leading to postoperative recession, peri-implantitis, and bone resorption. The use of collagen matrices does not always lead to complete rebuilding of the gingiva volume. The application of mesenchymal stromal cells (MSCs) simultaneously with collagen materials represents a promising approach for the restoration of soft gingival tissues. However, short-term effects of MSCs-enriched collagen grafts after gingival augmentation have not yet been studied properly. Mucograft and Mucoderm matrices were implanted in rabbits (n = 12) simultaneously with the intraoperative injection of rabbit bone marrow-derived mesenchymal stromal cells (BM-MSCs) or without cells. Collagen matrices were implanted under the flap or by the surface technique without intentional primary closure. The samples were harvested seven days after implantation, histological staining with hematoxylin and eosin, and immunohistochemical staining for VEGF, IGF1, and TGF were performed. The use of Mucoderm led to better augmentation outcomes on day 7 compared with Mucograft (p < 0.0001). Gingival augmentation in combination with the local administration of BM-MSCs led to better regeneration of the soft gingival tissues independently of the type of implanted collagen matrices (p < 0.0001). Furthermore, injection of BM-MSCs significantly enhanced gingival vascularization and epithelization with a clear positive correlation between vascular growth and epithelial response. Administration of BM-MSCs in combination with various collagen materials may potentially improve gingiva regeneration.