Differential privacy is the gold standard for privacy preserving data analysis, which is crucial in a wide range of disciplines. Vertex colouring is one of the most fundamental graph problems. In this work, we study vertex colouring in the differentially private setting. We consider edge-differential privacy, in which the edges of the graph are the private information that should be protected. To satisfy non-trivial privacy guarantees under this notion of privacy, a colouring algorithm needs to be defective: a colouring is d-defective if a vertex can share a colour with at most d of its neighbours. Without defectiveness, any edge-differentially private colouring algorithm needs to assign n different colours to the n different vertices. We show the following lower bound for the defectiveness: any \(\epsilon \) -edge differentially private algorithm that returns a c-vertex colouring of a graph of maximum degree \(\varDelta > 0\) with high probability must have defectiveness at least \(d \in \varOmega \left( \log n /(\epsilon + \log c)\right) \) . We complement our lower bound by presenting an \(\epsilon \) -differentially private algorithm for \(O\left( \varDelta / \log n+\epsilon ^{-1}\right) \) -colouring a graph with defectiveness at most \(O\left( \log n\right) \) .