The phase transition phenomenon is one of the central problems of statistical mechanics. It occurs when the model possesses multiple Gibbs measures. In this paper, we consider a three-state SOS (solid-on-solid) model on a Cayley tree. We reduce description of Gibbs measures to solving of a non-linear functional equation, each solution of which corresponds to a Gibbs measure. We give some sufficiency conditions on the existence of multiple Gibbs measures for the model. We give a review of some known (translation-invariant, periodic, non-periodic) Gibbs measures of the model and compare them with our new measures. We show that the Gibbs measures found in the paper differ from the known Gibbs measures, i. e, we show that these measures are new.