There was a lot of support for an expedition to cross Australia. In Melbourne, the biggest exploring expedition in Australian history, the Victorian Exploring Expedition, was being organized for the crossing. This became known as the Burke and Wills expedition, named after its two leaders, Robert O'Hara Burke and William John Wills. Stuart knew that he would be able to travel further and faster by only going with a small group. In March 1860, with Kekwick, Benjamin Head and 13 horses, Stuart left Chambers Creek and headed north. They were the first Europeans to enter central Australia. They reached the Finke River, the MacDonnell Ranges, and the strange rock formation Stuart called Chambers Pillar. On 23 April, Stuart worked out that they were at the very centre of Australia. He named a small hill near the spot Mount Sturt, after Charles Sturt. Stuart and Kekwick climbed the hill and raised the British flag. Stuart wrote that the flag would be a sign to the Aborigines "...that the dawn of liberty, civilization, and Christianity is about to break upon them." The name was later changed to Central Mount Stuart. From here Stuart tried to go northwest to reach the Victoria River. This took them into the Tanami Desert, but they could not find water and were forced to go back.
They continued to travel north, beyond the site of the town of Tennant Creek. On 26 June they reached a creek, now called Attack Creek, about north of Adelaide. A large group of Aborigines from a group called the Warramunga, attacked the explorers. The Warrumunga threw boomerangs at the explorers, and then set fire to the grass. Stuart and his men fired their guns at the Warrumunga, but Stuart does not say in his diary if any were killed or injured. The men quickly left the creek and went south.
Stuart decided they could not get any further north because they were running out of food, water was scarce and the horses were in poor condition. He wrote "...I think it would be madness and folly to attempt more." The return journey was very difficult. Stuart could only ride for a few hours a day; on one day he just dug a hole in the sand and curled up in it. Head was so hungry he stole food, which left them with even less. Their clothes were only torn rags and their bodies were covered in bruises caused by scurvy. Stuart wrote in his diary that "My men have now lost all their former energy...and move about as if they were a hundred years old. It is sad to see them..." Stuart wrote in his diary that sores on his hands had made them to painful to be used and he could only just sit in the saddle. He gums had become so sore and his teeth so loose that he could only eat flour boiled in water. He wrote on 16 May that "...I almost wished that death would come and relieve me from my fearful torture..." The medicines he had with him did not help.
The explorers made their way back to Adelaide as Burke and Wills were starting their journey north from Melbourne. Stuart was treated as a hero when he arrived in Adelaide. In 1859 the Royal Geographical Society in London presented him with gold watch. This was given to the explorer Count Paul Strzelecki to take back to Australia.
The cost of Stuart's exploring had been paid for by Chambers. Because of this, Stuart would not make his journals and maps available to the public. This led to claims that Stuart had not really travelled that far north and that he was lying about his discoveries. In Victoria it was even said that Stuart had not really gone north, but had been hiding in a cellar in Adelaide.
The public and the newspapers began to talk about a race across the continent of Australia. Could Stuart, experienced and used to moving quickly, beat the better equipped, but very slow moving Burke and Wills expedition. After their failures with Babbage and Tolmer's expeditions, the South Australian government now believed that Stuart would succeed if he had enough support. They gave £2,500 to set up another expedition and provided ten armed men to protect Stuart from any more attacks by the Aborigines. Chambers agreed to supply more horses and to pay Stuart and Kekwick's wages. In Victoria, a policeman was sent off to tell Burke to get going to the Gulf of Carpentaria as fast as possible, but Burke had already heard about Stuart's planned trip. Burke divided his group in two, and leaving most of his supplies behind at Menindee on the Darling River, he headed north to Cooper Creek.
On 1 January 1861, Stuart with a group of 12 men and 49 horses set off from Chambers Creek. The hot weather made it hard to find water and many waterholes from his earlier trips were dry. In February Stuart sent back two men with five horses. They reached the northern border of South Australia at about the same time that Burke and Wills reached the Gulf of Carpentaria. He was able to travel 240 km north of Attack Creek, where he found a large waterhole he called Glandfield Lagoon, after the mayor of Adelaide. Chambers later changed the name on Stuart's maps to Newcastle Waters, after the Duke of Newcastle, a British politician. From here Stuart again looked for a way to go north west to the Victoria River, but he was unable to find water. With the food running out, the men becoming sick, and horses in poor condition, Stuart again decided to return to Adelaide. Burke and Wills had not returned to Cooper Creek and were missing.
Stuart was presented with the Royal Geographical Society's Patron's Medal for 1861.
Stuart set out on his third attempt to cross Australia on 25 October 1861. This expedition was called the Great Northern Exploring Expedition. The group was: John McDouall Stuart, William Darton Kekwick, Francis William Thring, William Patrick Auld, Stephen King Jnr., John William Billiatt, James Frew Jnr., Heath Nash, John Woodforde, John McGorrery and Frederick George Waterhouse.
McGorrey was a blacksmith who would be able to fix the shoes on the group's 78 horses. Waterhouse was a naturalist who would be able to keep a scientific notes of their discoveries. Stuart was injured when a horse stood on his right hand, and remained behind for a month to recover. He learned about the deaths of Burke and Wills at Cooper Creek.
The group left Chambers Creek on 8 January 1862 moving fast, covering between 30 and 50 kilometres a day. The fast pace meant that in the first three weeks eight horses died and Woodforde left and went back. Stuart left some of the supplies behind and cut the amount each man was allowed to eat. At Mount Hay in central Australia, they were again attacked by Aboriginal warriors, but they were no match for the group's guns and several may have been killed.
They reached Newcastle Waters in three months, and then took a week to rest. Stuart spent the next five weeks searching for water. He finally found a series of waterholes, creeks and rivers which meant the whole group were able to continue to the north. He gave up trying to reach the Victoria River. When they got to the Roper River, which had been explored by Ludwig Leichhardt in 1845, he knew he could easily go west to the Gulf of Carpentaria, but instead chose to continue north. Auld later said that "...the mosquitos and flies were terrible. Our hands, feet and necks were blistered with their bites." They crossed Arnhem Land, and made the way along the edge of what is now Kakadu National Park. He followed the Adelaide River, but when the ground became too soft and muddy, they went further north to the Mary River and eventually reached the sea.