Certain black branes are unstable toward fluctuations that lead to non-uniform mass distributions. We study static, non-uniform solutions that differ only perturbatively from uniform ones. For uncharged black strings in five dimensions, we find evidence of a first order transition from uniform to non-uniform solutions.