We report two patients who developed a tracheo-innominate artery fistula (TIF) after tracheostomy. Contrast-enhanced computed tomography revealed a pseudoaneurysm of the innominate artery protruding into the trachea. Stent grafts were deployed for the innominate artery via two different access routes: the transfemoral approach and the right carotid artery approach. Endovascular stent-graft repair resulted in complete exclusion of the TIF and control of the bleeding from the tracheal stoma. At 12- and 16-month follow-ups, neither patient had clinical signs of graft infection, recurrent fistulization, or ischemic complications. It is feasible and useful to employ the carotid artery approach for stent-graft implantation in patients who have vascular anatomical limitations for the transfemoral approach. Endovascular repair of TIF by stent grafting is a minimally invasive treatment that can be tolerated by patients in poor clinical condition, and is a feasible alternative to surgical treatment.