A group of businessmen from The Dalles, Oregon, and vicinity incorporated The Dalles, Portland & Astoria Navigation Company (DP&AN) in 1890, in response to what people in the region viewed as excessive freight and passenger rates charged by steamboat companies operating between The Dalles and Portland, Oregon, particularly the Oregon Railway & Navigation Company (OR&N). In 1891, the DP&AN started operating two sternwheel steamers, the Regulator and Dalles City, and competed successfully against the OR&N. The DP&AN built a large warehouse at The Dalles, which facilitated shipment of wheat and wool from the region's farms to Portland, and constructed or leased wharves on both sides of the Columbia River.

The company was based at The Dalles until May 1902, when it was sold to the Columbia River & Northern Railway Company (CR&NR). Portland business interests dominated the CR&NR, which was building a railroad line between Lyle and Goldendale, Washington, and wanted to add river connections to Portland. CR&NR moved the company's headquarters to Portland, leaving The Dalles with a local agent, but the riverboat service continued to operate under the DP&AN name.

In 1905, Northern Pacific quietly obtained control of the company through a subsidiary, the Northwestern Improvement Company, and control was transferred to the Spokane, Portland & Seattle Railway in March 1908. The DP&AN stock was sold in 1915 to Drake C. O'Reilly, operator of the Diamond O Navigation Company, but the corporation was not dissolved until 1919, when its remaining assets were transferred to the Diamond O.