Old and new algorithms for the Maximum Satisfiability problem are studied. We first summarize the different heuristics previously proposed, i.e. the approximation algorithms of Johnson and of Lieberherr for the general Maximum Satisfiability problem, and the heuristics of Lieberherr and Specker, Poljak and Turzik for the Maximum 2-Satisfiability problem. Then we propose an exact algorithm which can be used for problems of moderate size, as well as the specialization of two recent local search algorithmic schemes, the Simulated Annealing method of Kirkpatrick, Gelatt and Vecchi, and the Steepest Ascent Mildest Descent method. The resulting algorithms, which avoid being blocked as soon as a local optimum has been found, are shown empirically to be more efficient than the heuristics previously proposed in the literature.