A significant amount of Yukon’s highway infrastructure is constructed on warm, ice-rich permafrost interlaced with ice wedges. Reconstruction of the North Alaska Highway 10-15 years ago induced thawing of the permafrost. As a result, the highway is continually subjected to severe settlements and longitudinal cracking. Currently, increased attention is being given to the problem of permafrost thawing underneath infrastructure due to the global focus on climate change. Yukon Highways and Public Works has undertaken an extensive research project aimed at finding cost-effective construction techniques to reduce permafrost thawing underneath the highway embankment. Several test sections along a 600m length of highway were constructed in April-June 2008. Mitigation techniques being tested include: air convection embankments (ACE), heat drains, longitudinal air ducts, light-coloured aggregate surfacing, side slope snow clearing, and snow sheds. The test sections are instrumented with thermistors, surface temperature loggers, and weather monitoring equipment. The primary goals of the research are to find methods suitable for rehabilitation of existing embankments, thereby reducing the ongoing maintenance costs over the life cycle of the highway and improving the ride and safety of the highway. The examination of the cost and constructability of the test sections, covered in this paper, is the first step in evaluating the potential of the mitigation techniques. The analysis includes descriptions of the procedures used for construction, specific construction challenges, and recommendations for future work. As well, the costs of implementing the various techniques have been compiled and compared.