A proposal submitted under the Virginia Public-Private Transportation Act by FD/MK, Ltd. in 1995 included the option of tolling the new highway. The firm indicated it could build the route by 2000 at a cost of $250 million if tolls were charged at $2.00 in each direction.6 The Commonwealth Transportation Board unanimously approved the route as a private toll road in 1996, but estimates increased to $389 million when debt service and financing was included (cost estimates were later be recanted to $300 million).7 The firm renamed the route Pocahontas Parkway and reduced the scale of the freeway to four lanes overall. An agreement between the state and FD/MK, Ltd. was finalized on June 3, 1998, clearing the way for $324 million in road work.8
Also known as the Airport Connector, construction of State Route 895 commenced on October 13, 1998. Completion of the route was planned in April 2002. It instead opened in two phases, with eastbound traffic using the toll road on May 22, 2002. Pocahontas Parkway westbound was completed on September 20, 2002.9
The 2001 Virginia official state map labelled SR 895 under construction as Interstate 895. Subsequent maps show the toll road as a state route. Planning documents and the project location map for SR 895 in 2001 also referred to Pocahontas Parkway as I-895.
SR 895 / Pocahontas Parkway is built to Interstate standards, but the Federal Highway Administration denied granting the toll road an Interstate designation because the environmental document and 60% of design costs were paid with federal-aid funds. The law stated that federal-aid funds may be used for a toll Interstate for feasibility studies, but not for design or construction.9