The question of whether nuclear deterrence "mattered" or "worked" during the Cold War is place of a lot of scholarly disagreement. It is easy to wave a hand and say, "ah, they didn't do X because they were deterred," but it is a lot harder to actually point to any reasons to believe that. Occasionally one has archival sources, around particular events (e.g. the Cuban Missile Crisis) which make it clear that the fears of imminent nuclear war caused one side or the other to modify behavior (and even with the CMC, it is a tricky thing — there was a lot going on, there, and there were un-deterred actors as well, like Castro). But it is a tricky thing, because deterrence is, at its core, a psychological effect (I threaten something you value and thus modify your behavior), and such things do not always leave archival traces.

In many key instances, there are reasons to think that fear of widespread nuclear war was not the reason for certain outcomes. The Korean War, for example, could easily have seen the US use nuclear weapons without any possibility of a Soviet response in kind (aside from the fact that the USSR only had a handful of weapons at the time, it had no means of delivering them far beyond their local borders, and the US by contrast already had a fairly credible global reach and hundreds of atomic bombs). There are other places (e.g. the USSR in Afghanistan) where the non-use of nuclear weapons likely had nothing to do with deterrence (because the idea that a full-scale nuclear war would erupt on the basis of a very localized proxy war is improbable — if the Soviets had used tactical nuclear weapons in the Soviet-Afghan War, or the US had used them in Vietnam, there is no reason at all that such use would compel a response that could lead to full annihilation).

We also do have instances of states doing things that they thought had a high likelihood of provoking a nuclear response. Saddam Hussein, for example, thought that it was highly likely the US would use nuclear weapons against him in the Persian Gulf War, but continued his actions anyway. (The Duelfer Report discusses this, I believe — it is a curious instance of someone explicitly not being deterred even when nuclear strike was not really being threatened.)

A lot of the "deterrence kept the peace" arguments are based not on actual examination of records or interviews with participants, but in a version of "Mutually Assured Destruction" rationality that was rarely actually accepted by the participants in these conflicts. That is, the US military and often its civilian leaders did not really accept that there was such a thing as "Mutually Assured Destruction" — they believed there were different levels of nuclear war, some of them "winnable," and often sought the possibility of a first-strike status against the USSR, just in case it was necessary. They also explicitly embraced the doctrine of tactical nuclear weapons at various points in the Cold War.

In general, it is worth keeping in mind that the US had an overwhelming strategic advantage over the USSR until the 1970s, and that the USSR did not have a reliable way of striking the continental US at all with nuclear weapons until the 1960s. The reasons for the US maintenance of the "nuclear taboo" (the non-use of nuclear weapons) are fairly complex and not at all just about deterrence.

That being said, the possibility of nuclear exchange certainly loomed in the back of the minds of these leaders, and could often be considered something that did not need stating explicitly. So this is a very hard thing to work out. To ask what would have happened in the Cold War had nuclear weapons not existed is such a massive counterfactual that it is hard to say anything sensible about it. We can say, for example, that it doesn't seem that the threat of nuclear war was the only thing kept Stalin from, say, pushing Westward after World War II — there were plenty of other reasons for him not to do that. But can we say what would have been if the bomb had not been developed? Not with any certainty, obviously, and we know that Stalin was deeply affected by the bombing of Hiroshima.

So this is a tough question, and an active area of research in the area of international security and diplomatic history. On the "nuclear taboo" in general, Nina Tannenwald's The Nuclear Taboo: The United States and the Non-Use of Nuclear Weapons Since 1945 (Cambridge University Press, 2007), is a definitive work.