Nació en la ciudad de Buenos Aires, en el barrio de Congreso, habitado mayoritariamente por criollos e inmigrantes de diferentes orígenes. En ese activo foco de cultura popular transcurrió su infancia y su adolescencia, convirtiéndose en los años 20 en un poeta y letrista de gran popularidad y de hábitos bohemios. En su juventud también fue boxeador.
Sus tangos, muchas veces sentenciosos y moralizantes, con descripciones de sus personajes, recurrían abundantemente al lunfardo, el argot local de la región del Río de la Plata. Su mejor etapa creativa abarcó hasta principios de los años 30.
En 1920 envió al diario Ultima hora, ya desaparecido, un poema titulado "Por la pinta", recibiendo 5 pesos como retribución. Los versos de dicho poema llamaron la atención de Carlos Gardel y de su compañero de dúo, José Razzano, que le pusieron música, creando el tango "Margot". Éste era una amarga crítica a la muchacha humilde y bonita que se acomoda y pervierte para escapar de su destino de pobreza.
Gardel grabó 21 temas de Celedonio, entre los cuales se encontraba uno de los mayores éxitos de toda su trayectoria: "Mano a mano", tango en el que un varón salda cuentas con la mujer a la que amó y le ofrece su desinteresada ayuda para cuando ella sea "descolado mueble viejo". Entre los otros tangos que grabó destacan "Mala entraña", "El bulín de la calle Ayacucho", "Viejo smoking", "Malevito", "Canchero" y "Pan". Este último contiene una descarnada crítica social, frente a la miseria que siguió a la crisis de 1930. Gardel se abstuvo por modestia de grabar uno de los mayores éxitos de Flores, "Corrientes y Esmeralda", referencia a una famosa esquina de Buenos Aires que forman la Avenida Corrientes y la calle Esmeralda, porque la letra aludía a mujeres que soñaban con su pinta.
Por razones comerciales, durante varios años Flores escribió exclusivamente para Rosita Quiroga, una notable cantante de fuerte carácter arrabalero y poco refinada. Con el paso de los años, los tangos de Celedonio comenzaron a formar parte de los repertorios de numerosos cantantes, desde Ignacio Corsini y Alberto Gómez, hasta Edmundo Rivero y Julio Sosa.
Otras letras que aunaron valor y éxito fueron las de "Muchacho", "Viejo coche", "Sentencia" (una canción protesta), "Atenti, pebeta" (tema de corte humorístico), "Pobre gallo bataraz", "Si se salva el pibe" y "Por qué canto así". "La musa mistonga", compuesto por Celedonio y grabado por Rosita Quiroga el 1 de marzo de 1926, fue la primera grabación que utilizó el sistema fonoeléctrico en Argentina.
Cuando murió, llevaba ya cuatro años la imposición de una férrea censura gubernamental sobre las letras de tango, de las que se suprimía todo término lunfardo y cualquier referencia social o moral que no coincidiera con las tesis del gobierno creado a raíz del golpe militar del 4 de junio de 1943. Las letras de las composiciones de Celedonio fueran modificadas tanto que amargaron los últimos años de vida de Celedonio. La censura fue desapareciendo después, pero él no vivió para verlo.