NATO’s Deterrence and Defense Posture Review (DDPR, 2012), concluded that “the Alliance’s nuclear force posture currently meets the criteria for an effective deterrence and defense posture.” In addition to the strategic nuclear forces of France, the United Kingdom, and the United States, NATO’s “posture” notably included, then and now, some 200 B-61 “tactical” nuclear bombs stored at sites in five longtime member states. Since release of the DDPR, NATO relations with Russia have deteriorated. It would appear that the American B-61 nukes, soon to be improved through a multibillion-dollar life extension program, are destined to stay in Europe. Beneath the surface, however, linger disquieting questions about the fabled three-C’s of NATO’s deterrence – its military capability, its credibility and its communication to potential adversaries and partners alike. This paper suggests six nuclear deterrence reforms that NATO should consider following the Warsaw Summit in July 2016 in order to regain the credibility it once had during the Cold War.