Tracheoinnominate artery fistula is a critical complication of tracheostomy. The most important factors influencing patient outcome are prompt diagnosis, immediate control of bleeding with a patent airway, and emergency operation with or without interruption of the innominate artery. Here, we report a case of tracheoinnominate artery fistula in a 40-year-old woman with cerebrovascular accident who was successfully managed with an aorta-axillary artery bypass.