Prime Minister RG Menzies secured a double dissolution of parliament, and another federal election was held in December 1955. This time the Coalition won ten seats from Labor. Among those won on the preferences of the 'anti-Communist' Labor Party group was the seat of Wannon, which went to Malcolm Fraser. When the Governor-General, Sir William Slim, opened the new parliament on 15 February 1956, 25-year-old Malcolm Fraser was the youngest member. RG Menzies' Minister for External Affairs, RG Casey, had family connections with the Fraser's, and remained a friend of Malcolm Fraser.
Malcolm Fraser and Tamara (Tamie) Beggs, whose family also ran a western Victorian property, were married a year later, one day short of his first parliamentary anniversary. The following year the couple moved to Canberra. As a backbencher, Fraser served on the Parliamentary Joint Committee on Foreign Affairs from 1962. With the two younger children at school, in 1964 Malcolm and Tamie Fraser made an official trip overseas. Fraser had been one of two parliamentarians to win a grant to study overseas, and in Washington he studied United States policy development. The other grant was won by Labor member Gough Whitlam.
On Robert Menzies' retirement in 1966, Prime Minister Harold Holt appointed Malcolm Fraser to his first ministry. Like Menzies, Holt had an inner Cabinet of twelve, and an 'outer' ministry. He included Annabelle Rankin as Housing Minister, and Fraser as Army Minister, in his outer ministry of thirteen. Malcolm Fraser was Army Minister for two years (1966-68), under three prime ministers. The first Australian troops had been despatched by the Menzies government in May 1965. In his first year as Army Minister, Fraser visited the troops in Vietnam, and also made official visits to Thailand, Laos, Malaysia and the Philippines.
John Gorton reshuffled Cabinet a month after he became Prime Minister, and allocated the portfolio of Education and Science to Malcolm Fraser. Though still an 'outer' portfolio, this was a period of expanding departmental responsibilities, with growth in tertiary education and increased government funding to private schools. After fourteen years as a government member of the House of Representatives, Malcolm Fraser finally became a member of the Cabinet. John Gorton allocated him the Defence portfolio after the federal election in October 1969, during the Vietnam war. Fraser, however, developed an uneasy relationship with his Prime Minister and early in 1971 their disagreements reached a critical point. Fraser charged Gorton with disloyalty to him in a conflict with senior Army officials. On 8 March 1971 Fraser resigned the Defence portfolio. Like Joseph Lyons and Robert Menzies before him, Fraser's resignation from Cabinet precipitated his Prime Minister's demise.
William McMahon became Prime Minister on 10 March 1971. McMahon appointed Fraser as Minister for Education and Science in August 1971. Malcolm Fraser served under five prime ministers in his seven years as a minister. When the Labor Party won the federal election on 2 December 1972, Malcolm Fraser moved to the Opposition benches for the first time in his parliamentary career. On 3 August 1973, Billy Snedden, who replaced William McMahon as Liberal Party leader, appointed Fraser shadow Minister for Industrial Relations. In 1971, In July 1974, Fraser used his speech at a commemorative dinner at the Melbourne Institute of Technology to contrast the ideals and realities of Liberal leadership. In August he wrote an article for the Melbourne Herald arguing that the Liberal Party had lost its sense of purpose and direction, and needed a leader who would reassert Liberal principles. He pursued this theme in his Robert Garran memorial lecture the same year and in an article in Australian Quarterly.
With shadow minister Tony Street and party official David Kemp on his side, Fraser's first leadership attempt on 26 November 1974 was followed by months of less direct challenges to Snedden. Then, on 21 March 1975, a leadership ballot was held and Snedden was defeated by Fraser, with Phillip Lynch remaining deputy leader. With Malcolm Fraser as Leader of the Opposition and Gough Whitlam as Prime Minister, the two men who as backbenchers had been awarded leadership grants ten years before, were now antagonists on the floor of the House of Representatives. The contest was brief. On 15 October 1975, Fraser set in motion the events leading to Whitlam's dismissal by the Governor-General when he announced that the Opposition would refuse passage through the Senate of the Budget Bills until Whitlam called an election. Justifying this decision, he claimed revelations about the government's attempts to bypass the Loans Council to obtain funds overseas indicated 'extraordinary and reprehensible circumstances' which warranted an electoral verdict on the government's actions.
Australia experienced its most severe constitutional crisis in October-November 1975 as the Opposition, now led by Fraser, refused to pass Budget Bills through the Senate, delaying the funding of government operations. Fraser said the Opposition would not grant supply until the government called a general election. Political deadlock followed as Whitlam rejected Fraser's demands for an election. The constitutional and financial crisis caused by the Senate's refusal to pass the Budget climaxed when J.R. Kerr, the Governor-General, withdrew Whitlam's commission as Prime Minister on 11 November 1975. Immediately after dismissing Whitlam, Kerr commissioned Fraser as interim Prime Minister pending a general election, then dissolved parliament.
Following an extremely rancorous election campaign, Fraser's Liberal-National Country Party won a landslide victory against the ALP at a general election on 13 December 1975. They won 91 seats (out of 127) in the House of Representatives and control of the Senate with a 6-seat majority. At a general election in December 1977, Fraser retained a huge majority in the House of Representatives (86 seats from a total of 124) and maintained control of the Senate. He easily won the next general election in October 1980, although the ALP won back 14 seats from the Liberals, and gains by the Australian Democrats in the Senate broke the government's control of the upper house. Despite an undeserved reputation for conservatism and determination to slash government expenditure, Fraser's Liberal-National Party coalition continued and extended the process of reform begun under the previous ALP government. Among its innovations were these:Although Fraser's government introduced many innovations, it was criticised by some Liberals for not initiating economic reform when it had the opportunity. Fraser proved a true conservative on economic issues, for example resisting economic deregulation and tariff reform. Fraser travelled widely as both Minister and Prime Minister: to Asia, Africa, North America, the Pacific and Europe. He became a prominent figure in 'CHOGM' (Commonwealth Heads of Government Meetings), and hosted CHOGM in Sydney in February 1978 and in Melbourne and Canberra from September-October 1981.
A new 'centre' party, the Australian Democrats, formed in May 1977 by Don Chipp, a former Liberal Minister who had become disillusioned with the party under Fraser's leadership. Chipp took one of two Senate seats the Democrats won seven months later at the general election. At the next general election, in October 1980, they won five Senate seats, gaining balance of power in the Senate.
On 3 February 1983, Fraser gained a double dissolution of parliament and called a general election. He hoped to gain an advantage from the disunity in the federal parliamentary ALP over R.J.L. Hawke's challenges to W.G. Hayden's leadership of the ALP. Twenty minutes later Hayden resigned as ALP leader, allowing Hawke to assume leadership. Following an election campaign largely focusing on Fraser's and Hawke's personalities, the ALP won a 25-seat majority in the House of Representatives. With 30 out of 64 Senate seats, the ALP had the largest number of Senators, but the success of the Democrats in winning 5 seats gave them the balance of power in the Senate. In conceding defeat early on 6 March 1983, the morning following the election, Fraser announced his intention of resigning from the Liberal leadership. He resigned from parliament five days later, on 11 March, and later that day the parliamentary Liberal Party elected Andrew S. Peacock to replace him as leader.
On quitting parliament, Fraser retired to 'Nareen', but remained active in public affairs. In 1985 he was chosen as a member of an international group of 'eminent persons' seeking to end apartheid in South Africa by encouraging dialogue between the opposed racial communities. (He had been a real critic of apartheid since entering parliament.) Later, he became a political columnist for the Australian newspaper and head of Care Australia, an international relief agency with special interests in delivering aid to poverty stricken nations in Africa.