O'Malley was educated at a primary school in New York City, then worked in his uncle's bank and as an insurance and real estate salesman, travelling widely around the United States. While in Texas O'Malley founded a church taking the title of "First Bishop of the Waterlily Rock Bound Church, the Red Skin Temple of the Cayuse Nation" in order to take advantage of a government land grant then being offered to churches. In 1881 O'Malley married Rosy Wilmot who died from tuberculosis shortly before she was due to give birth in 1886. O'Malley found he had contracted the disease from her and in 1888, having been given six months to live, he sailed for Queensland, Australia.
Landing at Port Alma, O'Malley apparently took up residence in a cave at Emu Park where he befriended an aboriginal, Coowonga, who cared for him until he recovered. Now healthy, O'Malley decided to walk the 2,100 km from Emu Park to Adelaide in South Australia, arriving in 1893. In South Australia he again worked as an itinerant insurance salesman, also preaching evangelical Christianity and temperance. In 1895 he settled in Gawler, South Australia, and in 1896 he was elected as a member for Encounter Bay in the South Australian House of Assembly as a radical democrat, opposed to the wealthy landowners who then dominated colonial politics. Calling himself a Christian Socialist, his most popular platform among conservatives was to rid hotels of barmaids "hired for their physical attributes rather than their prowess in drawing ale". Although unsuccessful himself, in 1909 laws were passed to require registration of barmaids who were now required to be a member of the owner's family.
O'Malley's narrow win in the 1896 election has been credited to his popularity among religious leaders and conservatives for his extreme puritan views but it seems his popularity with women voters was a bigger factor. Women were much taken by his appearance and O'Malley's "oratorial buffoonery" was the popular topic of discussion throughout South Australia. He called hotels "drunkeries", alcohol was "stagger juice", opponents were "diabolical rapscallions" and he referred to himself as the "bald headed Eagle from the Rocky Mountains".
O'Malley was defeated in 1899, and the following year he moved to Tasmania, the smallest of the Australian colonies. Here a tall, fashionably dressed American preaching the Gospel and radical democracy drew immediate attention, and in 1901 he was elected as the member for Darwin, one of Tasmania's five members in the first Australian Parliament. Although there was no Labour Party in Tasmania at this time, he joined the Labour Caucus when the Parliament assembled in Melbourne.
Historian Gavin Souter describes O'Malley at this time:
O'Malley's monstrously overgrown persona seemed to be inhabited simultaneously by a spruiker from Barnum's three-ring circus, a hell-and-tarnation revivalist, and a four-flushing Yankee Congressman. He was a moderately big man, auburn-haired with watchful grey eyes and a red-brown beard, wearing a wide-brimmed felt hat, blue-grey suit with huge lapels and a low-cut vest, loose cravat with a diamond collar stud, and in the centre of his cream silk shirt-front a fiery opal.
O'Malley was thus one of the more prominent and colourful members of the Parliament, but his radical ideas were not widely accepted, and many regarded him as a charlatan. He became a prominent advocate of a national bank as a means of providing cheap credit for farmers and small businessmen.
He was not a member of Chris Watson's first Labour ministry in 1904, or of Andrew Fisher's first ministry in 1908. But in April 1910 the Caucus elected him to the ministry of Fisher's second government. In the same year he married again, to Amy Garrod.
O'Malley became Minister for Home Affairs, and played a prominent role in selecting the site of the future capital of Australia, Canberra. He declared American architect Walter Burley Griffin winner of the town planning competition. On 20 February 1913, O'Malley drove in the first peg which marked the start of the development of the city. He was also present at the ceremony for the naming of Canberra on 12 March 1913.
As a teetotaller he was responsible for the highly unpopular ban on alcohol in the Australian Capital Territory. He could also claim credit for beginning the building of the Trans-Australian Railway from Port Augusta to Perth.
He also agitated for the establishment of the Commonwealth Bank of Australia, a state-owned savings and investment bank, although he was not the bank's sole inspirer, as he later liked to claim. He later wrote that he had led a "torpedo squad" in Caucus to force a reluctant Cabinet to establish the bank, but historians do not accept this. Prime Minister Fisher was the bank's principal architect. Partly to allay fears of "funny money" aroused by O'Malley's populist rhetoric, Fisher ensured that the bank would be run on firmly "sound money" principles, and the bank as established did not provide easy credit for farmers as the radicals desired.
O'Malley's other legacy was the spelling of "Labor" in the Australian Labor Party's title in the American style. He was a spelling reform enthusiast and persuaded the party that "Labor" was a more "modern" spelling than "Labour". Although the American spelling has not become established in Australia, the Labor Party has preserved the spelling.
Labor was defeated at the June 1913 election, and when it returned to office in October 1914, O'Malley was not re-elected to the Cabinet. In October 1915, however, Fisher retired and O'Malley returned to office in the first ministry of Billy Hughes, again as Minister for Home Affairs. But a year later the government split over the determination of Hughes to introduce conscription for Australia's contribution to World War I. O'Malley resigned from Hughes's Cabinet in protest and became an outspoken anti-conscriptionist.
Hughes called an election in May 1917, and O'Malley was very narrowly defeated in his northern Tasmanian seat by a Nationalist candidate. He stood for the seat again in 1919, and for another seat in 1922, but he never returned to elective office. Although he was only 59 at the time of his defeat, he retired to Melbourne and devoted his time to building up his own legend, particularly in relation to the Commonwealth Bank, and to polemical journalism on a variety of pet causes. He lived to be 95, outliving his nemesis Hughes. At the time of his death he was the last surviving member of the first Australian Parliament.
O'Malley's importance in developing the national capital is remembered in Canberra with the suburb of O'Malley being named after him. A pub in Canberra, King O'Malley's Irish Pub in Civic, is also named after him - this is a tongue-in-cheek reference to his above-mentioned role in an unpopular alcohol ban in the Australian Capital Territory. O'Malley is the subject of a 1970 musical play The Legend of King O'Malley by Michael Boddy and Bob Ellis.