Disclosed and claimed herein are a natural coloring formulation for coloring hair, and methods of its use. The coloring formulation includes a catechol-based precursor and an oxidizing agent. Additionally an alkalizing agent may be present. The formulation is substantially free of organic solvents, co-solvents and diluents.