In September of 1854, Frederick was ordained to preach the gospel in the Bendigo gold mines. He held the office of a priest at the time. After preaching there for a while, and also working for gold, Fred and Clement set out for Zion with a group of fellow saints. They stopped at Tahiti, and "…after five weeks of indescribable kinds of times [they] put-in in distress at the Sandwich Islands, the vessel so leaky she could hardly swim."

They reached Honolulu in the Sandwich (Hawaiian) Islands on July 5, 1855, after a voyage of eleven weeks from Australia. Some of the passengers stayed in the Islands to make a little more money before going to Zion, but the rest put to sea again about a week later. After they got clear of the land they were becalmed for eight days waiting for the wind to blow again. When it did start to blow, it was almost a hurricane. After some difficulty, it was decided that the vessel was not seaworthy, so they returned to Honolulu.

There was some confusion among the saints, as many of them had given all they had for their passage to Utah. The able-bodied men were asked to give what they had in order to help the aged and the women and children. Frederick gave what money he had and then later turned over the gold nuggets he had sewn in his clothing, which were worth about $1,000.

While in the Islands, Fred was called to serve as a missionary and was ordained an elder on the 16th of August, 1855. He was sent to the island of Molokai to labor. As he didn’t have any money, he sold a pair of boots to pay for his passage to Molokai and to obtain some things he needed. The native saints enjoyed hearing him and his companion sing in English, and whenever they went anywhere to visit, that is about the first thing they were asked to do. Frederick accepted what help his brother was able to send him, but mostly the missionaries had to depend on the natives, among whom they worked, for food, lodging and even their clothing. Many times they went without these necessities and went hungry frequently.

At one time the elders traveled from Molokai over to Lahaina. While there, they were given some bread—the first Elder Hurst had eaten for five months. Mostly their diet consisted of fish, potatoes (salt is mentioned frequently), poi and fresh fruit. On February 8, 1856, Frederick recorded, “We had three meals today for the first time for I will not venture to say how long. We fasted about three days this week.”

Most of their traveling was done on foot; sometimes they went twenty or more miles in a single day. He made many journal entries similar to the following: “My boots had just given out when we got to this place. One of the brethren gave me a pair of low shoes, so when I have begged a pair of socks somewhere I shall be set up.” However, before he did get any socks, he made at least one long journey without any and ended up with very miserable feet.

Frederick William Hurst was released from the Sandwich Island Mission on October 6, 1856. Fred and his brother, Charles Clement, set sail for San Francisco on November 8, 1856 and arrived there on November 23, 1856. The brothers found what work was available, eventually going to the Redwoods to split posts. They returned to San Francisco in the spring with the intention of going to Salt Lake Valley. Frederick was again called to be a missionary—this time in California. In fulfilling his duties he again did a lot of walking and traveled from one settlement to another, preaching the gospel wherever he could find people to listen. His labors in California were cut short, as all the saints were advised to go to the Salt Lake Valley to help meet the advance of Johnston’s Army. He left California October 12, 1857, in company with a group of saints to travel to Salt Lake City via San Bernardino.