We build a maximum entropy model for skin detection. This model imposes constraints on various marginal distributions. Parameter estimation as well as optimization cannot be tackled without approximations. We propose to use a tree approximation of the pixel lattice. Parameter estimation is then reduced to the estimations of color histograms for neighbor pixels. Moreover, the belief propagation algorithm permits to obtain fast solution for skin probability at pixel locations. We assess the performance on the Compaq database.