In today’s globalized world, nations are increasingly concerned about how they are perceived by their publics, often carefully planning and executing policies to maintain a positive identity or shed a negative image. While some countries are able to execute nation branding, others are not. Using the Nigerian experience as a case study, this article shows how the character of a state can undermine its capacity for successful nation branding. We argue that countries are judged not just by what they say but also by what they do, and that inherent contradictions such as sectarian violence, ethnic tension, and corruption underline Nigeria’s underdevelopment and its reputation at home and abroad. We assess this trajectory in the context of state fragility and “prebendalization” politics in a country with a powerful colonial legacy, and suggest a duality of order and disorder involving formal and informal structures of governance that impinge significantly on re-branding efforts.