A mechanism is said to be renegotiation-proof if it is robust against renegotation both before and after it is played. We ask the following three related questions: (1) what kind of environments or mechanism design problems admit renegotiation-proof implementation? (2) what kind of social choice rules are implementable in a way that is renegotiation-proof? and (3) what kind of mechanisms are renegotiation-proof? We provide characterization results for environments, social choice rules, and mechanisms that facilitate renegotiation-proof implementation in complete information settings, and in incomplete information settings with independent private values. For incomplete information settings with correlated interdependent values we provide sufficient conditions for renegotiation-proof implementation. Importantly, our results imply that some common mechanism design problems do not admit the existence of any renegotiation-proof mechanism.