Labor came to power later in October 1941 under John Curtin, following the defeat of the Fadden government in Parliament. In 1943 Curtin won a huge election victory. During 1944 Menzies held a series of meetings to discuss forming a new anti-Labor party to replace the moribund UAP. This was the Liberal Party, which was launched in early 1945 with Menzies as leader. But Labor was firmly entrenched in power and in 1946 Curtin's successor, Ben Chifley, was comfortably re-elected. Comments that "we can't win with Menzies" began to circulate in the conservative press.

Over the next few years, however, the anti-communist atmosphere of the early Cold War began to erode Labor's support. In 1947, Chifley announced that he intended to nationalise Australia's private banks, arousing intense middle-class opposition which Menzies successfully exploited. In 1949 a bitter coal-strike, engineered by the
Communist Party, also played into Menzies's hands. In December 1949 he won a smashing election victory and again became Prime Minister.

The ALP retained control of the Senate, however, and made Menzies's life very difficult. In 1951 Menzies introduced legislation to ban the Communist Party, hoping that the Senate would reject it and give him an excuse for a double dissolution election, but Labor let the bill pass. It was subsequently ruled unconstitutional by the High Court. But when the Senate rejected his banking bill, he called a double dissolution and won control of both Houses.

Later in 1951 Menzies decided to hold a referendum to change the Constitution to permit him to ban the Communist Party. The new Labor leader, Dr H.V. Evatt, campaigned against the referendum on civil liberties grounds, and it was narrowly defeated. This was one of Menzies's few electoral miscalculations. He sent Australian troops to the Korean War and maintained a close alliance with the United States.

Economic conditions, however, deteriorated, and Evatt was confident of winning the 1954 elections. Shortly before the elections, Menzies announced that a Soviet diplomat in Australia Vladimir Petrov (see Petrov affair), had defected, and that there was evidence of a Soviet spy ring in Australia, including members of Evatt's staff. This Cold War scare enabled Menzies to win the election. Labor accused Menzies of arranging Petrov's defection, but this has since been disproved: he had simply taken advantage of it.

The aftermath of the 1954 election caused a split in the Labor Party, and Menzies was comfortably re-elected over Evatt in 1955 and 1958. By this time the post-war economic boom was in full swing, fuelled by massive immigration and the growth in housing and manufacturing that this produced. Prices for Australia's agricultural exports were also high, ensuring rising incomes. Labor's rather old-fashioned socialist rhetoric was no match for Menzies and his promise of stability and prosperity for all.

Labor's new leader, Arthur Calwell, gave Menzies a scare after an ill-judged squeeze on credit - an effort to restrain inflation - caused a rise in unemployment. At the 1961 election Menzies was returned with a majority of only two seats. But Menzies was able to exploit Labor's divisions over the Cold War and the American alliance, and win an increased majority in 1963. An incident in which Calwell was photographed standing outside a South Canberra hotel while the ALP Federal Executive (dubbed by Menzies the "36 faceless men") was determining policy also contributed to the 1963 victory. This was the first "television election," and Menzies, although nearly 70, proved a master of the new medium. He was created a Knight of the Thistle in the same year.

In 1965 Menzies made the fateful decision to commit Australian troops to the Vietnam War, and also to reintroduce conscription. These moves were initially popular, but later became a problem for his successors. Despite his pragmatic acceptance of the new power balance in the Pacific after World War II and his strong support for the American alliance, he publicly professed continued admiration for links with Britain, exemplified by his admiration for Queen Elizabeth II, and famously described himself as "British to the bootstraps". In 1954 extraordinary crowds came to see and cheer her. Over the decade, Australia's ardour for Britain and the monarchy faded somewhat, but Menzies' had not. The Queen toured again in 1963. At a function, Menzies quoted Elizabethan poet Barnabe Googe, "I did but see her passing by, and yet I love her till I die," for which he attracted public scorn.