Elk was originally constructed at Houghton, Washington, and launched under the name Katherine. Katherine was 44 ft (13.41 m) long, 44 ft (13.41 m) on the beam, and rated at 14.25 registered tons.Katherine operated on Lake Washington, and by 1895, was owned by Capt J.C. O'Connor, who had been born in New York in 1846. O'Connor had been involved with steamboats on Lake Washington since 1874, when he had worked on the steamer Chehalis
In 1896, Capt. O.G. Olsen (d. 1924) bought the steamboat Katherine. Olsen was a native of Norway who came to Pacific Coast in 1883. Olsen rebuilt Katherine as a tug and took the vessel to Puget Sound to operate out of Tacoma as a tug under the name of Elk, the first vessel of what became the Olsen Tug Boat Company.
In 1909, while operating under the Seattle concern of Crosbie Towing Co., Elk was towing a barge loaded with telephone cable intended for the Kitsap County Telephone Company, Elk went aground near Restoration Point. As a result the vessel suffered extensive damage, including breaking the tail shaft, rudder shaft and keel. Elk was not a total loss, and the vessel was able to be removed to the King and Winge shipyard in West Seattle where repairs were made.