New decoding algorithms for binary linear codes based on the concave-convex procedure are presented. Numerical experiments show that the proposed decoding algorithms surpass Belief Propagation (BP) decoding in error performance. Average computational complexity of one of the proposed decoding algorithms is only a few times greater than that of the BP decoding.