In 1983, the Province of Newfoundland and Labrador started construction of the Trans Labrador Highway (TLH). Upgrading and new construction was undertaken in three phases starting in1997. Phase II (Red Bay to Cartwright), a 325 km all-weather gravel highway passing through uninhabited and undeveloped wilderness country, is intersected by 150 watercourses, ranging from small streams to large rivers (Alexis and St. Lewis). These two large rivers created difficult challenges for the planning and design of the 110 m single span truss bridges, including site optimization, road travel minimization and maintenance through mountainous terrain and/or traversing deep tidal inlets. Environmental considerations using survey data from 1823 hydrometric surveys (depth soundings) were employed along with a hydrological/hydraulic study (tidal effects), as well as river and ocean ice concerns. Bridge structures over the Alexis and St. Lewis Rivers consisted of steel truss designs with steel grid deck and reinforced concrete abutments. Problems encountered included route layout and selection, geoscience considerations, hydrology, hydraulics, causeway construction, bridge launching and environmental issues. Weak clayey silts had to sustain a load of up to a 30 m high causeway at the abutments. Part of Phase III is the forthcoming bridge over the Churchill River. Problems include the search for a good crossing point, hydraulic design and hydrological considerations, foundation concerns, ice forces and erection methods. Completion of the TLH will facilitate new opportunities in tourism, forestry and mining; provide improved access to health and education; and reduce travel costs.