exh99_1.htm

NEWS RELEASE

NORTH AMERICAN ENERGY PARTNERS ANNOUNCES

COMPLETION OF AMENDMENT TO INDENTURE REGARDING ITS

9.125% SERIES 1 SENIOR UNSECURED DEBENTURES DUE 2017

Edmonton, Alberta, October 17, 2013 - North American Energy Partners Inc. (“NAEP” or “the Company”) (TSX/NYSE: NOA) today announced that it has executed a Second Supplemental Trust Indenture which amends the Indenture under which its outstanding 9.125% Series 1 Senior Unsecured Debentures due 2017 (the “Notes”) were issued. Such amendment is as outlined in the previously announced consent solicitation, which expired on October 9, 2013 at 5:00 pm (Toronto time).

Pursuant to the terms of the consent solicitation, valid consents in respect of an aggregate principal amount of $71,151,000 of Notes were delivered, equal to approximately 94.9% of the outstanding Notes. The aggregate consent fee of $1,500,000 will be paid on a pro-rata basis to holders who have provided valid consents and such consent fee for each $1,000 principal amount of Notes is equal to approximately $21.08.

About the Company

North American Energy Partners Inc. (www.naepi.ca) is one of the largest providers of heavy construction and mining 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.

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.

For further information, please contact:

David Brunetta, CMA

Senior Financial Manager, Investor Relations

North American Energy Partners Inc.

Office: (780) 969-5574

Email: dbrunetta@nacg.ca

Since 1953 • Heavy Construction & Mining

Suite 300, 18817 Stony Plain Road Edmonton, Alberta T5S 0C2 Canada Phone 780.960.7171 Fax 780.969.5599