The first things which he set himself to learn, on board ship, were the Maori language and the art of navigation. The first he studied with a native teacher, the second he learnt from the Bishop, and he proved an apt pupil in both. In a few months he became qualified to act as master of the Mission ship, and the speaking of a new language was to him only a matter of weeks. His earliest letters show how quickly he came to understand the natives. He was ready to meet any and every demand made upon him, and to fulfil duties as different from one another as those of teacher, skipper, and storekeeper. His head-quarters, during his early months in New Zealand, were either on board ship or else at St. John's College, five miles from Auckland. But, before he had completed a year, he was called to accompany the Bishop on his tour to the Islands and to make acquaintance with the scene of his future labours.

Bishop Selwyn had wisely limited his mission to those islands which the Gospel had not reached. The counsels of St. Paul and his own sagacity warned him against exposing his Church to the danger of jealous rivalry. So long as Christ was preached in an island or group of islands, he was content; he would leave them to the ministry of those who were first in the field. Many of the Polynesian groups had been visited by French and English missionaries and stations had been established in Samoa, Tahiti, and elsewhere; but north of New Zealand there was a large tract of the Pacific, including the New Hebrides and the Solomon Islands, where the natives had never heard the Gospel message. These groups were known collectively as Melanesia, a name hardly justified by facts,[38] as the inhabitants were by no means uniform in colour. If the Solomon Islanders had almost black skins, those who lived in the Banks Islands, which Patteson came to know so well, were of a warm brown hue such as may be seen in India or even in the south of Europe. Writing in the very last month of his life, Patteson tells his sisters how the colour of the people in Mota 'is just what Titian and the Venetian painters delighted in, the colour of their own weather-beaten boatmen'.

Selwyn had visited these islands intermittently since 1849, and had thought out a plan for spreading Christianity among them. With only a small staff of helpers and many other demands on his time, he could not hope to get into direct contact with a large population, so widely scattered. His work must be done through natives selected by himself, and these must be trained while they were young and open to impressions, while their character was still in the making. So every year he brought back with him from his cruise a certain number of Melanesian boys to spend the warmer months of the New Zealand year under the charge of the missionaries, and restored them to their homes at the beginning of the next cruise. At Auckland, with its soldiers, sailors, and merchants, the boys became familiar with other sides of European life beyond the walls of the Mission School; and their interest was stimulated by a close view of the strength to be drawn from European civilization. By this system Selwyn hoped that they on their return would spread among the islanders a certain knowledge of European ways, and that their relatives, seeing how the boys had been kindly treated, would feel confidence in the missionaries and would give them a hearing. This policy commended itself to Patteson by its practical efficacy; and though he modified it in details, he remained all his life a convinced adherent of the principle. Slow progress through a few pupils, selected when young, and carefully taught, was worth more than mere numbers, though too often in Missionary reports success is gauged by figures and statistics.

These cruises furnished the adventurous part of the life. Readers of Stevenson and Conrad can picture to themselves to-day the colour, the mystery, and the magic of the South Seas. Patteson, with his reserved nature and his dread of seeming to throw a false glamour over his practical duties, wrote but sparingly of such sights; but he was by no means insensitive to natural beauty and his letters give glimpses of coral reefs and lagoons, of palms and coco-nut trees, of creepers 100 feet long trailing over lofty crags to the clear water below.

He enjoyed being on board ship, with his books at hand and some leisure to read them, with the Bishop at his side to counsel him, and generally some of his pupils to need his help. They had many delightful days when they received friendly greeting on the islands and found that they were making real progress among the natives. But the elements of discomfort, disappointment, and danger were rarely absent for long. For a large part of each voyage they had some forty or fifty Melanesian boys on board, on their way to school or returning to their homes. The schooner built for the purpose was as airy and convenient as it could be made; yet there was little space for privacy. The natives were constitutionally weak; and when illness broke out, no trained nurses were at hand and Patteson would give up his own quarters to the sick and spend hours at their bedsides. Sometimes they found, on revisiting an island, that their old scholars had fallen away and that they had to begin again from the start. Sometimes they had to abstain from landing at all, because the behaviour of the natives was menacing, or because news had reached the Mission of some recent quarrel which had roused bitter feeling. The traditions of the Melanesians inclined them to go on the war-path only too readily, and both Selwyn and Patteson had an instinctive perception of the native temperament and its danger.

However lightly Patteson might treat these perils in his letters home, there was never complete security. To reassure his sisters he tells them of 81 landings and only two arrows fired at them in one cruise; and yet one poisoned arrow might be the cause of death accompanied by indescribable agony. Even when a landing had been effected and friendly trading and talk had given confidence to the visitors, it might be that an arrow was discharged at them by some irresponsible native as they made for their boats.

These voyages needed unconventional qualities in the missioner; few of the subscribers in quiet English parishes had an idea how the Melanesian islanders made their first acquaintance with their Bishop. When the boat came near the shore, the Bishop, arrayed in some of his oldest clothes, would jump into the sea and swim to land, sometimes being roughly handled by the breakers which guarded the coral bank. It was desirable not to expose their precious boat to the cupidity of the natives or to the risk of it being dashed to pieces in the surf, so the Bishop risked his own person instead. He would then with all possible coolness walk into a gathering of savages, catch up any familiar words which seemed to occur in the new dialect, or, failing any linguistic help, try to convey his peaceful intentions by gesture or facial expression. When an island had been visited before, there was less reason to be on guard; but sometimes the Bishop had to break to relatives the sad news that one of the boys committed to his care had fallen a victim to the more rigorous climate of New Zealand or to one of the diseases to which these tribes were so liable. Then it was only the personal ascendancy won by previous visits that could secure him against a violent impulse to revenge.

All practical measures were tried to establish friendly relations with the islanders; and when people at home might fancy the Bishop preaching impressively to a decorous circle of listeners, he was really engaged in lively talk and barter, receiving yams and other articles of food in return for the produce of Birmingham and Sheffield, axe-heads which he presented to the old, and fish-hooks with which he won the favour of the young. But such brief visits as could be made at a score of islands in a busy tour did not carry matters far, and the memory of a visit would be growing dim before another chance came of renewing intercourse with the same tribe. Selwyn felt it was most desirable that he should have sufficient staff to leave a missionary here and there to spend unbroken winter months in a single station, where he could reach more of the people and exercise a more continuous influence upon them. Patteson's first experience of this was in 1858, when he spent three months at Lifu in the Loyalty Islands, a group which was later to be annexed by the French.

A sojourn which was to bear more permanent fruit was that which he made at Mota in 1860. This was one of the Banks Islands lying north of the New Hebrides, in 14° South Latitude. The inhabitants of this group showed unusual capacity for learning from the missionaries, and sufficient stability of character to promise lasting success for the work carried on among them. Mota, owing to the line of cliffs which formed its coast, was a difficult place for landing; so it escaped the visits of white traders who could not emulate the swimming feats of Selwyn and Patteson, and was free from many of the troubles which such visitors brought with them. Once the island was reached, it proved to be one of the most attractive, with rich soil, plenty of water, and a kindly docile population. Here, on a site duly purchased for the mission, under the shade of a gigantic banyan tree, on a slope where bread-fruit and coco-nuts (and, later, pine-apples and other importations) flourished, the first habitation was built, with a boarded floor, walls of bamboo canes, and a roof of coco-nut leaves woven together after the native fashion so as to be waterproof. Here, in the next ten years, Patteson was to spend many happy weeks, taking school, reading and writing when the curiosity of the natives left him any peace, but in general patiently conversing with all and sundry who came up, with the twofold object of gathering knowledge of their dialect and making friends with individuals. While he showed instinctive tact in knowing how far it was wise to go in opposing the native way of life, he was willing to face risks whenever real progress could be made. After he had been some days in Mota a special initiation in a degrading rite was held outside the village. Patteson exercised all his influence to prevent one of his converts from being drawn in; and when an old man came up and terrorized his pupils by planting a symbolic tree outside the Mission hut, Patteson argued with him at length and persuaded him to withdraw his threatening symbol. But apart from idolatry, from internecine warfare, and from such horrors as cannibalism, prevalent in many islands, he was studious not to attack old traditions. He wanted a good Melanesian standard of conduct, not a feeble imitation of European culture. He was prepared to build upon the foundation which time had already prepared and not to invert the order of nature.

In writing home of his life in the island Patteson regularly depreciates his own hardships, saying how unworthy he feels himself to be ranked with the pioneers in African work. But the discomforts must often have been considerable to a man naturally fastidious and brought up as he had been.