Background: We performed gene therapy for critical limb ischemia in thromboangiitis obliterans (TAO) by the intramuscular administration of plasmids of the vascular endothelial growth factor gene (VEGF 165) with or without bone marrow-derived stem cells. Methods: The 21 patients were randomly assigned to three groups: A—with dual therapy, cells and plasmid; B—plasmid only; and C—control group, where patients received intramuscular injections of saline. Serum VEGF levels, the ankle–brachial index (ABI), transcutaneous oxygen pressure (TcPO2), and the rest pain measured by the visual analog scale (VAS) were determined sequentially before treatment, and then 1 and 3 months after treatment. Results: In the treatment groups, serum VEGF levels increased by 4 weeks and returned to baseline values after 3 months. ABI after 12 weeks increased by an average of 0.18 in group A, and 0.09 in group B and group C. TcPO2 increased by an average of 17.3 mmHg in group A, 14.1 mmHg in group B, and 10.7 mmHg in group C. The largest pain decrease was observed in group A and averaged 5.43 less pain intensity. Conclusions: Gene therapy using the VEGF plasmid along with or without bone marrow-derived mononuclear cells administered intramuscularly into an ischemic limb in TAO is a safe and effective therapy.