In 1890, 27-year-old Capt. Gordon C. Greene bought the steamboat H.K. Bedford and entered the Pittsburgh-Wheeling packet trade, carrying freight and passengers between the two cities. The same year he married his childhood sweetheart, Mary Becker, and they began life together on the Bedford. Within a few years Mary had learned the river and became one of the few women to become a licensed steamboat pilot.

The H. K. Bedford, which eventually sank in the Ohio River after having been sold to other owners, began Pittsburgh-Charleston service in 1896. Greene Line boats, headquartered in Cincinnati, operated on the Kanawha River from then until the end of the packet boat era in the 1930s. In 1903, Captain Greene built the side-wheel packet Greenland. The Greenland would be the largest side-wheeler ever to offer regular service on the Kanawha River. In 1904, the Greenes acquired the Cincinnati, Portsmouth, Big Sandy & Pomeroy Packet Co., adding four more packet boats to their fleet.

Capt. Gordon Greene died on January 27, 1927. Mary B. Greene, with sons Chris and Tom, continued to operate the company. Capt. Mary B. Greene, sometimes known as "Maw" Greene, became a legend on the rivers as both a pilot and master on her company's boats. She died in 1949.

Between 1890 and 1947, the Greene Line owned or operated 27 steamboats. The company acquired the famous Delta Queen in 1947, the last steamboat the Greene Line would own. In 1969, Overseas National Airway acquired the Greene Line and in 1973 changed the name to The Delta Queen Steamboat Co. The company now operates the Delta Queen, Mississippi Queen, and the American Queen on the Mississippi River system, as well as the Columbia Queen on the Columbia River in Oregon.