Tracheostomy is increasingly used in patients receiving prolonged mechanical ventilation (PMV). Tracheo-innominate artery fistula (TIF) is a rare but potentially life-threatening complication of tracheostomy. The incidence of TIF formation usually peaks 7 to 14 days after tracheostomy. Surgical intervention with full or partial median sternotomy followed by ligation of the innominate artery is recommended for definitive management of this fatal complication. Nonetheless, effective hemostasis by endovascular procedures in selected patients has been reported. We herein present a case of TIF that developed on the very next day after a tracheostomy in a 72-year-old man with PMV, which was successfully treated by endovascular embolization.