ex99_1.htm

NORTH AMERICAN ENERGY PARTNERS ANNOUNCES $127

MILLION OIL SANDS CONTRACT

Also Updates Status on Canadian Natural Contract Discussions

Calgary, Alberta, [month][day], 2011 - North American Energy Partners Inc. (“NAEP” or “the Company”) (TSX/NYSE: NOA) today announced it has been awarded a $127 million heavy civil construction contract with Fluor Canada Limited at Syncrude Canada Ltd’s (Syncrude) Base Mine and provided an update on the progress of discussions with Canadian Natural Resources Limited (Canadian Natural).

The new contract at Syncrude is the first of several large construction contracts to be let relating to the mine train relocations1 at Syncrude’s Base and Aurora Mines. NAEP completed the preliminary earthworks related to this project in the spring of 2011. This new contract represents a significant increase in the Company’s work-scope on this site through to August 2012 and covers the construction of roads, grading and civil works for the shear key foundation at Syncrude’s Base Mine. The foundation will provide the base for construction of the second phase of the project, a mechanically stabilized earth (MSE) wall and ore crushing facility, construction of which is expected to be undertaken in the summer of 2012 under a separate contract yet to be awarded.

“We were very pleased to be the successful bidder on this initial phase of Syncrude’s mine train relocation,” said Rod Ruston, President and CEO of NAEP. “Not only does this add to an already strong backlog of winter work for our fiscal 2012 year but we believe that the opportunity to demonstrate our capabilities on this initial project, coupled with our reputation as the preeminent MSE wall constructor in the oil sands, strongly positions us to secure additional work on Syncrude’s mine train relocation projects.”

Canadian Natural Contract Discussions

The previously announced joint working committee, which was formed to collect and analyze market data relating to cost inflation in the Fort McMurray business environment, is expected to make recommendations to NAEP and Canadian Natural in early to mid September. At that time, NAEP and Canadian Natural will enter into discussions to agree upon any index adjustments to be made and to determine any

1 A “mine train” is a modular process for crushing and mixing the oil sands with warm water to facilitate the extraction of bitumen. The process includes three components: a crusher, which breaks down the bitumen ore after it has been mined; a surge bin that regulates the oil sands’ feed into the process; and a mix box in which warm water is added to the oil sands to form a slurry suitable for pumping. The resulting slurry is then pumped to extraction in a pipeline, which conditions the oil sands for separation. In the oil sands, the mine train is relocated about every 10 – 15 years as the ore is mined and the mine footprint expands away from the upgrader.

NEWS RELEASE

additional contract amendments that the parties may deem to be beneficial to the ongoing operation of the contract.

“Both parties are working to get this issue resolved as expeditiously as possible,” said Mr. Ruston. “Our goal is to resolve the past issues and develop a sustainable solution that ensures a continued strong working relationship for the remaining four years of the contract. We are pleased with the progress to date and both parties are eager to get the resolution behind us so we can focus on the safe and efficient restart of operations at Canadian Natural’s site in January.”

NAEP expects this process will be completed prior to the anticipated restart of its overburden removal operations on the site in January, 2012. NAEP will continue to recognize revenue on the contract only to the extent of costs incurred until a formal agreement has been reached and any contract amendments have been executed by both parties. NAEP does not intend to disclose information relating to the joint working committee recommendations, however, NAEP will inform market participants of any material contract adjustments upon final resolution.

Additional information on the contract negotiations and impacts on NAEP’s financial results can be found in the Company’s Management’s Discussion and Analysis for the period ended June 30, 2011, which is available on SEDAR and EDGAR.

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. 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 our control. Important factors that could cause actual results to differ materially from those in 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 our debt instruments, exchange rate fluctuations, weather conditions, performance of our customers, access to equipment, changes in laws and

NEWS RELEASE

ability to execute transactions. Undue reliance should not be placed upon forward-looking statements and we undertake no obligation, other than those required by applicable law, to update or revise those statements.

For more complete information about us you should read our disclosure documents that we have 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.

-30-

For further information, please contact:

Kevin Rowand

Director, Investor Relations & Strategic Planning

North American Energy Partners Inc.

Phone: (780) 960-4531

Fax: (780) 960-7103

Email: krowand@nacg.ca

NEWS RELEASE

for up to three weeks. These evacuations negatively affected segment revenues by approximately $12 million for the period and reduced margins due to increased costs resulting from lower productivity. Subsequent to the wildfire evacuation at the Horizon site, Canadian Natural suspended activity under the long-term overburden removal contract until January 2, 2012 while they repair and restart their plant, which was damaged by a plant fire earlier in the year.

For the three months ended June 30, 2011, Heavy Construction and Mining segment profit margin was 13.3% of revenue, compared to 13.6% last year. The current year segment margin included the negative impact of recognizing zero-margin on revenues from the Canadian Natural overburden removal contract. NAEP has formed a joint working group with Canadian Natural that will be responsible for identifying indices that will more closely reflect the inflationary conditions that have occurred in the market place. The working group has been meeting to discuss the relevant facts and we expect this group to deliver recommendations by the target date of August 31, 2011 and that the recommended new indices will apply both prospectively and retrospectively. Excluding revenues and profits from the Canadian Natural overburden contract from both periods, segment margin would have been 16.7% of revenue in the current three-month period and comparable in the same period last year.