A tracheo-innominate artery fistula is an uncommon but frequently fatal complication of tracheostomy. Rarely, it can also occur in laryngectomized patients. We report a post-laryngectomy, post-radiotherapy patient using a metal tracheostomy tube, who developed a tracheo-innominate artery fistula about two months after radiotherapy. To our knowledge this is only the second reported case in a laryngectomized patient. The computed tomography (CT) angiography findings helped confirm the diagnosis and the patient was successfully managed by surgical exploration and ligation of the innominate artery. Coagulase negative Staphylococcus aureus was cultured from a tracheal swab. The clinical features, CT angiography findings, management protocols and possible aetiological factors are discussed.