La primera descripción formal fue realizada por el zoólogo holandés Coenraad Jacob Temminck en 1824 con el nombre binomial de Saxicola melanura.
[4][5] El colinegro común fue incluido como la especie tipo del género Cercomela, creado por Charles Lucien Bonaparte en 1856.
[6] Estudios filogenéticos realizados en 2010 y 2012 descubrieron que el género Cercomela era polifilético.
[9][10] El epíteto específico melanura deriva del griego clásico μελανουρος (melanouros) melas «negro» y oura «cola» que unidos significa «de cola negra».
La subespecie nominal O. m. melanura tiene las partes superiores de color gris ceniza azulado con las alas más oscuras y el obispillo y la cola negras.