Exhibit 99.1

NEWS RELEASE

NORTH AMERICAN ENERGY PARTNERS REACHES FINAL

CONTRACT AGREEMENT WITH CANADIAN NATURAL

RESOURCES

Calgary, Alberta, March 27, 2012 - North American Energy Partners Inc. (“NAEP” or “the Company”) (TSX/NYSE: NOA) today announced that it has reached final agreement with Canadian Natural Resources Limited (“Canadian Natural”)  on amendments to the long-term overburden removal and mining services contract between Canadian Natural and NAEP’s wholly-owned subsidiary, North American Construction Group Inc. (“NACG”).

The amending agreement finalizes certain past costs under the original contract, resulting in a payment of $34 million by Canadian Natural to NACG.  As a result, NAEP does not expect to record any additional revenue writedown associated with this contract.  The $34 million payment will be recorded as an increase in cash and cash equivalents with a corresponding reduction of unbilled revenue on the Company’s March 31, 2012 Consolidated Balance Sheet.

The general terms of the original contract related to work scope will remain in place, meaning NACG will continue providing overburden removal and tailings dyke construction services to Canadian Natural.  However, these services will now be performed under a revised payment structure that carries less risk than the unit-rate structure it replaces.  The new structure ensures a base margin for NACG with the opportunity to enhance margins by meeting mutually agreed upon performance targets.

“We are very pleased with the outcome of our negotiations,” said Rod Ruston, President and CEO of NAEP.  “The amended agreement helps ensure that we will be profitable on our work at the Horizon site, while remaining accountable for our operational and safety performance.  It also promises to strengthen our relationship with Canadian Natural by creating shared goals that offer a financial incentive to both parties to work together to reach clearly defined targets.”

In addition to the amending agreement, Canadian Natural has committed to accelerate the buyout of approximately 30% of the contract-related assets used by NACG on the Horizon site, some of which are owned outright by NACG and some of which are leased.  After settling outstanding lease obligations, NACG’s share of the proceeds from this transaction is expected to be approximately $40 million.  It is expected that

NEWS RELEASE

approximately 85% of the identified assets will be acquired by Canadian Natural over the next six weeks with the remaining transactions occurring as leases become due later in 2012.

NAEP intends to use the proceeds of the settlement and asset buyout to reduce the draw on its revolving credit facility and thus eliminate the need for the temporary increase to the facility that was secured in September 2011 to support an anticipated increase in working capital.  The temporary facility will be reduced in line with the timing of the receipt of funds from the asset sale and be eliminated when the bulk of the sales are completed, which is expected to be by June 2012.

“The finalizing of these contract negotiations significantly enhances our financial position and improves our margins and cash flow going forward, while also supporting our broader strategy of reducing our reliance on equipment leases,” added Mr. Ruston.  “Overall, we expect this settlement will contribute to stronger financial performance over the next 12 months.”

Conference Call and Webcast

Management will hold a conference call to discuss this contract amendment today, Tuesday, March 27, 2012 at 9:00 am Eastern time.

The call can be accessed by dialing:

Toll free: 1-877-407-8031

International: 1-201-689-8031

About the Company

North American Energy Partners Inc. (www.naepi.ca) is one of the largest providers of heavy construction, mining, piling and pipeline services in Western Canada.  For more than 50 years, NAEP has provided services to large oil, natural gas and resource companies, with a principal focus on the Canadian oil sands.  The Company maintains one of the largest independently owned equipment fleets in the region.

Forward-Looking Statements

The information provided in this release contains forward-looking statements. Forward-looking statements include statements preceded by, followed by or that include the words “may”, “could”, “would”, “should”, “believe”, “expect”, “anticipate”, “plan”, “estimate”, “target”, ‘project”, “intend”, “continue”, “further” or similar expressions. Examples of

NEWS RELEASE

such forward-looking statements include the expected sale of contract-related assets to Canadian Natural and the expected proceeds of such sale.  Actual results could differ materially from those contemplated by such forward-looking statements as a result of any number of factors and uncertainties, many of which are beyond NAEP’s control. Important factors that could cause actual results to differ materially from those in the forward-looking statements include: success of business development efforts, changes in oil and gas prices, availability of a skilled labour force, internal controls, general economic conditions, terms of the Company’s debt instruments, exchange rate fluctuations, weather conditions, performance of its customers, access to equipment, changes in laws and the ability to execute transactions, including the expected sale of certain assets to Canadian Natural. Undue reliance should not be placed upon forward-looking statements and NAEP undertakes no obligation, other than those required by applicable law, to update or revise those statements.

For more complete information about NAEP, you should read the Company’s disclosure documents filed with the SEC and the CSA. You may obtain these documents for free by visiting EDGAR on the SEC website at www.sec.gov or on the CSA website at www.sedar.com.

For further information, please contact:

David Blackley, CFO

North American Energy Partners Inc.

Phone: (403) 767-4827

Email: dblackley@nacg.ca

Bernie Robert

Vice President, Corporate

North American Energy Partners Inc.

Phone: (403) 767-4840

Email: brobert@nacg.ca