The 1951 U.S.-Icelandic Defense Agreement paved the way for a permanent U.S. military presence at the Keflavik base in Iceland, an outpost that played a crucial role in U.S. strategy during the Cold War. The article explores two gender-related aspects of the U.S.-Icelandic Cold War relationship: the restrictions on off-base movements of U.S. soldiers, and the secret ban imposed by the Icelandic government on the stationing of black U.S. troops in Iceland. These practices were meant to "protect" Icelandic women and to preserve a homogeneous "national body." Although U.S. officials repeatedly tried tohave the restrictions lifted, the Icelandic government refused to modify them until the racial ban was publicly disclosed in late 1959. Even after the practice came to light, it took another several years before the ban was gradually eliminated. Misguided though the Icelandic restrictions may have been, they did, paradoxically, help to defuse domestic opposition to Iceland's pro-American foreign policy course and thus preserved the country's role in the Western alliance.