for 30 years. In November he was appointed to the last three-decker constructed for the Royal Navy, HMS Victoria, in the Mediterranean. Life sailing in the Levant was considerably less dangerous, and normally only required the arrival of a British ship to settle a dispute. There was plenty of time for leave and Markham visited Turkey, Egypt, the Holy Land, Greece and the Aegean islands. Appointment to the fleet patrolling the eastern end of the Mediterranean was considered by many as less desirable than the western patrol which visited France and Italy, but the historical sites in the east suited Markham's interests. He kept a journal describing the places he visited, as he did throughout his life. One of his greatest delights was to meet Minna and Clements ashore and to accompany them on archaeological expedition in the region. In 1868, Markham was appointed first lieutenant of HMS Blanche on the Australia Station where he helped suppress "blackbirding", the illegal trading of slaves between Queensland and the South Sea Islands. This included time spent as an acting commander on HMS Rosario. The issue was not straightforward, because the Queensland government was ambivalent towards the trade, which provided workers for its plantations. Some of the native workers were pleased to be travelling to Queensland, while others hated all white men. A bishop and three others were murdered in one incident, and Markham led a party to Nukapu to exact revenge, destroying a local village. Although Markham's actions were supposedly fuelled by his righteous indignation at an attack upon churchmen, he was criticised in parliament and the press for overreacting. The admiralty, however, approved of his actions. Markham himself found the work more worthwhile than the Mediterranean posting, although it meant he no longer saw Clements and Minna. In 1869 he submitted a design to George Bowen, the Governor of New Zealand, for a national ensign for New Zealand. His proposal, incorporating the Southern Cross, was approved and remains in use to this day. On 29 November 1872 he was promoted to commander and spent the next six years engaged in Arctic Exploration. As a reward for his efforts in the British Arctic Expedition of 1876, he was promoted to captain. From 1879 to 1882 he was the captain of , the flagship of the Pacific Station. In 1883 he was appointed as captain of HMS Vernon, a naval torpedo school in