Dixon Denham was born at Salisbury Square, Fleet Street, London on New Year's Day, 1786, the son of James Denham, a haberdasher, and his wife Eleanor, née Symonds. The youngest of their three sons, Denham was educated at Merchant Taylors' School from 1794 to 1800; on leaving he was articled to a solicitor, but joined the army in 1811.
Initially in the 23rd Royal Welch Fusiliers, and later the 54th Foot, Denham served in the campaigns in Portugal, Spain, France, and Belgium, receiving the Waterloo Medal. Denham was considered a brave soldier, who had carried his wounded commander out of the line of fire at the Battle of Toulouse, and had become a close acquaintance of the Duke of Wellington, with whom he regularly corresponded. At the end of hostilities, Lieutenant Denham served at Cambray and with the occupation of Paris. Placed on half pay in 1818, he travelled for a time in France and Italy. In 1819, Denham entered the Royal Military College, Sandhurst, as a student, intending to become a staff officer in the Senior Department of the Royal Military College. He attracted the favourable attention of the Commandant of the College, Sir Howard Douglas, but became very bored; 'he was the kind of man who must have adventure or he rots', wrote a friend. Alas, he was also domineering, insecure, jealous, and possessed of a mean streak.
Denham had met the explorer Captain George Lyon on the latter's return to London from Africa, and became determined to join the British government's second mission to establish trade links with the west African states. Perhaps because of his influential acquaintances, Denham's wish was granted and, now promoted to Major, he was despatched by Lord Bathurst in the autumn of 1821 to join the other members of the mission, Dr Walter Oudney and Lt. Hugh Clapperton, arriving at Tripoli aboard the schooner Express on 19 November.
Denham brought with him instructions from the Colonial Office indicating that Oudney should remain at Bornu as Vice-Consul, while Denham and Clapperton were to 'explore the Country to the Southward and Eastward of Bornu, principally with a view to tracing the course of the Niger and ascertaining its Embouchure'. For reasons unknown, Denham was detained in Tripoli, and the mission proceeded to Murzuk, in Fezzan, without him on 23 February 1822. Denham eventually left Tripoli on 5 March with an escort of 210 mounted Arab tribesmen, reaching Murzuk only to find his two compatriots in a wretched condition, Clapperton ill of an ague, and Oudney with a severe cold. Moreover, he discovered that the local bey had forbidden their departure from the Fezzan while he was absent on a slave-raiding expedition, a restriction enforced by the removal of the mission's camels. Denham soon returned to Tripoli, to seek further funds, and to persuade the bashaw, Yusuf Karamanli, to provide the essential escort to protect the mission on its journey south to Bornu. He arrived back in Tripoli on 13 June 1822, his departure from the mission unlamented. He had already made himself unpopular, leading Clapperton to write to Sir John Barrow: 'His absence will be no loss to the Mission, and a saving to his country, for Major Denham could not read his sextant, knew not a star in the heavens, and could not take the altitude of the sun'.
Denham was to find the bashaw as obdurate as Murzuk's bey. Outraged, he decided to return to London to report the situation to Lord Bathurst and also seek promotion, so that he could return as commanding officer of the expedition. Boarding a ship bound for Marseilles, he warned the bashaw's lieutenants of his government's displeasure when it learned of the bashaw's 'duplicity'. Duly alarmed, the bashaw wrote to him, proposing that the 300 – man escort of a wealthy merchant about to depart for Bornu could, for a fee of 10,000 dollars to be shared with him, be persuaded to protect the mission as well. Denham received the letter while in quarantine in Marseilles. Still very angry, he sent an ill-judged letter to Bathurst complaining of Oudney's incompetence. The missal was not well received in London, and Denham found a letter awaiting him on his return to Tripoli, rebuking him for his lack of diplomacy, although acknowledging the frustrations he had endured. News of Denham's conduct left his compatriots at Murzuk dumbfounded. Oudney wrote a bitter letter of complaint about Denham to Hanmer Warrington, the British Consul in Tripoli, comparing Denham to a snake hidden in the grass. In an unfortunate breach of confidence, Warrington showed the letter to Denham, thereby souring relations within the mission party still further.