Adipose-derived stromal cells (ASCs) are suggested to be potent candidates for cell therapy of ischemic conditions due to their ability to stimulate blood vessel growth. ASCs produce many angiogenic and anti-apoptotic growth factors, and their secretion is significantly enhanced by hypoxia. Utilizing a Matrigel implant model, we showed that hypoxia-treated ASCs stimulated angiogenesis as well as maturation of the newly formed blood vessels in vivo. To elucidate mechanisms of ASC angiogenic action, we used a co-culture model of ASCs with cells isolated from early postnatal hearts (cardiomyocyte fraction, CMF). CMF contained mature cardiomyocytes, endothelial cells, and progenitor cells. On the second day of culture CMF cells formed spontaneously beating colonies with CD31+ capillary-like structures outgrowing from those cell aggregates. However, these vessel-like structures were not stable, and disassembled within next 5 days. Co-culturing of CMF with ASCs resulted in the formation of stable and branched CD31+ vessel-like structures. Using immunomagnetic depletion of CMF from vascular cells as well as incubation of CMF with mitomycin C-treated ASCs, we showed that in co-culture ASCs enhance blood vessel growth not only by production of paracrine-acting factors but also by promoting the endothelial differentiation of cardiac progenitor cells. All these mechanisms of actions could be beneficial for the stimulation of angiogenesis in ischemic tissues by ASCs administration.