Under the Securities Exchange Act of 1934
(Amendment No. 1)

(Name of Issuer)

(Title of Class of Securities)

(CUSIP Number)

(Name, Address and Telephone Number of Person
Authorized to Receive Notices and Communications)

(Date of Event which Requires Filing of this Statement)

If the filing person has previously filed a statement on Schedule 13G to report the acquisition that is the subject of this Schedule 13D, and is filing this schedule because of §§240.13d-1(e), 240.13d-1(f) or 240.13d-1(g), check the following box: o

Note: Schedules filed in paper format shall include a signed original and five copies of the schedule, including all exhibits. See §240.13d-7 for other parties to whom copies are to be sent.

* The remainder of this cover page shall be filled out for a reporting person's initial filing on this form with respect to the subject class of securities, and for any subsequent amendment containing information which would alter disclosures provided in a prior cover page.

The information required on the remainder of this cover page shall not be deemed to be "filed" for the purpose of Section 18 of the Securities Exchange Act of 1934 ("Act") or otherwise subject to the liabilities of that section of the Act but shall be subject to all other provisions of the Act (however, see the Notes).

(Continued on following pages)

SCHEDULE 13D/A

(1)  Includes 11,934,351 Series A Subordinated Units and 13,500,000 Series B Subordinated Units, each representing limited partner interests in the Issuer. The Series A Subordinated Units may be converted into Common Units on a one-for-one basis upon termination of the subordination period under certain circumstances, as set forth in the Second Amended and Restated Agreement of Limited Partnership of PAA Natural Gas Storage, L.P., as amended (the “Partnership Agreement”). The Series B Subordinated Units may be converted into Series A Subordinated Units on a one-for-one basis upon the satisfaction of certain operational and financial conditions or, if the subordination period has ended at the time the various operation and financial conditions are satisfied, into Common Units on a one-for-one basis, as set forth in the Partnership Agreement; provided, however, that any Series B Subordinated Units that remain outstanding as of December 31, 2018 will be automatically cancelled.

(2)  Based on the aggregate number of Common Units, Series A Subordinated Units and Series B Subordinated Units issued and outstanding as of July 31, 2013.

2

SCHEDULE 13D/A

(1)  Includes 11,934,351 Series A Subordinated Units and 13,500,000 Series B Subordinated Units, each representing limited partner interests in the Issuer. The Series A Subordinated Units may be converted into Common Units on a one-for-one basis upon termination of the subordination period under certain circumstances, as set forth in the Partnership Agreement. The Series B Subordinated Units may be converted into Series A Subordinated Units on a one-for-one basis upon the satisfaction of certain operational and financial conditions or, if the subordination period has ended at the time the various operation and financial conditions are satisfied, into Common Units on a one-for-one basis, as set forth in the Partnership Agreement; provided, however, that any Series B Subordinated Units that remain outstanding as of December 31, 2018 will be automatically cancelled.

(2)  Based on the aggregate number of Common Units, Series A Subordinated Units and Series B Subordinated Units issued and outstanding as of July 31, 2013.

3

SCHEDULE 13D/A

(1)  Includes 11,934,351 Series A Subordinated Units and 13,500,000 Series B Subordinated Units, each representing limited partner interests in the Issuer. The Series A Subordinated Units may be converted into Common Units on a one-for-one basis upon termination of the subordination period under certain circumstances, as set forth in the Partnership Agreement. The Series B Subordinated Units may be converted into Series A Subordinated Units on a one-for-one basis upon the satisfaction of certain operational and financial conditions or, if the subordination period has ended at the time the various operation and financial conditions are satisfied, into Common Units on a one-for-one basis, as set forth in the Partnership Agreement; provided, however, that any Series B Subordinated Units that remain outstanding as of December 31, 2018 will be automatically cancelled.

(2)  Based on the aggregate number of Common Units, Series A Subordinated Units and Series B Subordinated Units issued and outstanding as of July 31, 2013.

4

SCHEDULE 13D/A

(1)  Includes 11,934,351 Series A Subordinated Units and 13,500,000 Series B Subordinated Units, each representing limited partner interests in the Issuer. The Series A Subordinated Units may be converted into Common Units on a one-for-one basis upon termination of the subordination period under certain circumstances, as set forth in the Partnership Agreement. The Series B Subordinated Units may be converted into Series A Subordinated Units on a one-for-one basis upon the satisfaction of certain operational and financial conditions or, if the subordination period has ended at the time the various operation and financial conditions are satisfied, into Common Units on a one-for-one basis, as set forth in the Partnership Agreement; provided, however, that any Series B Subordinated Units that remain outstanding as of December 31, 2018 will be automatically cancelled.

(2)  Based on the aggregate number of Common Units, Series A Subordinated Units and Series B Subordinated Units issued and outstanding as of July 31, 2013.

5

Item 1.   Security and Issuer

This Amendment No. 1 to Schedule 13D (this “Amendment”) relates to the common units representing limited partner interests (the “Common Units”) of PAA Natural Gas Storage, L.P., a Delaware limited partnership (the “Issuer” or the “Partnership”), which has its principal executive offices at 333 Clay Street, Suite 1500, Houston, Texas 77002, and amends the Schedule 13D filed with the Securities and Exchange Commission (the “SEC”) on February 18, 2011 (the “Original Schedule 13D”) by Plains All American Pipeline, L.P., a Delaware limited partnership (“PAA”), PAA GP LLC, a Delaware limited liability company (“General Partner”), Plains AAP, L.P., a Delaware limited liability company (“AAP”), and Plains All American GP LLC (“GP LLC” and, collectively with PAA, General Partner and AAP, the “Reporting Persons”).

Except as otherwise specified in this Amendment, all items left blank remain unchanged in all material respects and any items that are reported are deemed to amend and restate the corresponding items in the Original Schedule 13D.  Capitalized terms used herein but not defined herein have the respective meanings ascribed to them in the Original Schedule 13D.

Item 2.   Identity and Background

In accordance with the provisions of General Instruction C to Schedule 13D, information concerning the general partners, executive officers, board of directors and each person controlling a Reporting Person, as applicable (collectively, the “Listed Persons”), required by Item 2 of Schedule 13D, is provided on Schedule 1 hereto and is incorporated by reference herein. To the Reporting Persons’ knowledge, none of Listed Persons has been, during the last five years, (i) convicted in a criminal proceeding (excluding traffic violations or similar misdemeanors), or (ii) a party to a civil proceeding of a judicial or administrative body of competent jurisdiction and as a result of such proceeding was or is subject to a judgment, decree or final order enjoining future violations of, or prohibiting or mandating activities subject to, federal or state securities laws or finding any violation with respect to such laws.

Item 3.   Source and Amount of Funds or Other Consideration

Item 3 of the Original 13D is hereby amended to add the following paragraph:

(c) Proposal

In connection with the transaction proposed by the Proposal described in Item 4 of this Amendment (which Item 4 is incorporated herein by reference), the Reporting Person anticipates that the funding for such transaction will consist of newly issued Common Units of PAA as described in Item 4, and cash in lieu of fractional Common Units payable from the working capital of PAA.

Item 4.   Purpose of Transaction

Item 4 of the Original Schedule 13D is hereby amended to add the following paragraphs:

On August 27, 2013, PAA delivered a proposal (the “Proposal”) to the independent directors (the “Independent Directors”) of PNGS GP LLC , the general partner of the Issuer, to acquire all of the outstanding Common Units of the Issuer that are held by unitholders other than PAA or its subsidiaries, for consideration of 0.435 Common Units of PAA for each outstanding Common Unit of the Issuer held by such unitholders, in a transaction to be structured as a merger of the Issuer with a wholly-owned subsidiary of PAA. The Proposal assumes the execution of definitive agreements on or before September 27, 2013 and closing prior to the end of 2013.  The Proposal also assumes a regular quarterly distribution by the Issuer in November equal to the common unit distribution paid by the Issuer in August 2013. The consummation of the transactions contemplated by the Proposal is subject to the approval of GP LLC, which is the general partner of AAP, which is the sole member of the General Partner (as the general partner of PAA), approval of a committee of independent directors of PNGS GP LLC (the “Conflicts Committee”), approval of the unitholders of the Issuer and negotiation and execution of a definitive agreement.

While the Proposal remains under consideration or negotiation by the Issuer and its Conflicts Committee, the Reporting Persons may respond to inquiries from the Issuer and the Conflicts Committee or its representatives. Each Reporting Person does not intend to update additional disclosures in its Schedule 13D regarding any other plans or proposals by PAA until a definitive agreement has been

6

reached, or unless disclosure is otherwise required under applicable securities laws. A copy of the Proposal is filed herewith as Exhibit 99.1 and is incorporated by reference into this Item 4.

Other than as described above, none of the Reporting Persons has any plan or proposals of the type referred to in clauses (a) through (j) of Item 4 of Schedule 13D, although they reserve the right to formulate such plans or proposals in the future.

Item 5.   Interest in Securities of the Issuer

Sub-Items (a), (b) and (c) of Item 5 of the Original Schedule 13D are hereby amended and restated in their entirety as follows:

(a) (1) PAA is the record and beneficial owner of 28,155,526 Common Units, as well as 11,934,351 Series A Subordinated Units and 13,500,000 Series B Subordinated Units, which represent all of the outstanding Subordinated Units of the Issuer. Based on there being 86,581,800 Common and Subordinated Units outstanding as of July 31, 2013, PAA’s Common Units and Subordinated Units represent 61.9% of the outstanding Common Units and Subordinated Units at such time. The Series A Subordinated Units may be converted into Common Units on a one-for-one basis upon termination of the subordination period under certain circumstances, as set forth in the Partnership Agreement. The Series B Subordinated Units may be converted into Series A Subordinated Units on a one-for-one basis upon the satisfaction of certain operational and financial conditions or, if the subordination period for the Series A Subordinated Units has ended at the time the operation and financial conditions are satisfied, into Common Units on a one-for-one basis, as set forth in the Partnership Agreement

PAA, as the sole member of PNGS GP LLC, the general partner of the Issuer, may also, pursuant to Rule 13d-3, be deemed to beneficially own the equity interest representing a 2% general partner interest and the incentive distribution rights (representing the right to receive increasing percentages of quarterly distributions in excess of specified amounts) in the Issuer held by PNGS GP LLC.

(2) The General Partner, AAP and GP LLC may, pursuant to Rule 13d-3, be deemed to be indirect beneficial owners of the securities held by PAA, described in (a)(1) above.

(b) The information set forth in Items 7 through 11 of the cover pages hereto is incorporated herein by reference. See Schedule 1 for the information applicable to the Listed Persons.

(c) Except as described in Item 3 above or elsewhere in this Schedule 13D, none of the Reporting Persons or, to the Reporting Persons’ knowledge, the Listed Persons has effected any transactions in the Common Units during the past 60 days.

Item 6.   Contracts, Arrangements, Understandings or Relationships with Respect to Securities of the Issuer

Item 6 of the Original Schedule 13D is hereby amended to add the following paragraph:

The information set forth under Item 4 and in Exhibit 99.1 is hereby incorporated by reference in this Item 6.

Item 7.   Material to be Filed as Exhibits

Item 7 of the Original Schedule 13D is hereby amended to add the following exhibits:

99.1*                                         Proposal Letter from Plains All American Pipeline, L.P. to the Independent Directors of the Board of Directors of PNGS GP LLC, dated August 27, 2013.

99.2                                                Joint Filing Statement among the Reporting Persons dated February 18, 2011 (incorporated herein by reference to Exhibit 99.C to the Original Schedule 13D filed on February 18, 2011).

*                 Filed herewith.

7

Signature

After reasonable inquiry and to the best of my knowledge and belief, I certify that the information set forth in this statement is true, complete and correct.

Date:      August 27, 2013

8

Signature

After reasonable inquiry and to the best of my knowledge and belief, I certify that the information set forth in this statement is true, complete and correct.

Date:      August 27, 2013

9

Signature

After reasonable inquiry and to the best of my knowledge and belief, I certify that the information set forth in this statement is true, complete and correct.

Date:      August 27, 2013

10

Signature

After reasonable inquiry and to the best of my knowledge and belief, I certify that the information set forth in this statement is true, complete and correct.

Date:      August 27, 2013

11

EXHIBIT INDEX

The Exhibit Index is amended to include the following exhibits:

99.1*                                         Proposal Letter from Plains All American Pipeline, L.P. to the Independent Directors of the Board of Directors of PNGS GP LLC, dated August 27, 2013.

99.2                                                Joint Filing Statement among the Reporting Persons dated February 18, 2011 (incorporated herein by reference to Exhibit 99.C to the Original Schedule 13D filed on February 18, 2011).

*                 Filed herewith.

12

Schedule I

Executive Officers(1)

Greg L. Armstrong

Address: c/o Plains All American Pipeline, L.P., 333 Clay Street, Suite 1600, Houston, Texas 77002

Principal Occupation: Chairman of the Board, Chief Executive Officer and Director of PNGS GP LLC and of Plains All American GP LLC

Citizenship: USA

Amount Beneficially Owned: 162,000

Harry N. Pefanis

Address: c/o Plains All American Pipeline, L.P., 333 Clay Street, Suite 1600, Houston, Texas 77002

Principal Occupation: Vice Chairman and Director of PNGS GP LLC and President and Chief Operating Officer of Plains All American GP LLC

Citizenship: USA

Amount Beneficially Owned: 117,000

Mark J. Gorman

Address: c/o Plains All American Pipeline, L.P., 333 Clay Street, Suite 1600, Houston, Texas 77002

Principal Occupation: Executive Vice President—Operations and Business Development of Plains All American GP LLC

Citizenship: USA

Amount Beneficially Owned: 6,000

Phillip D. Kramer

Address: c/o Plains All American Pipeline, L.P., 333 Clay Street, Suite 1600, Houston, Texas 77002

Principal Occupation: Executive Vice President of Plains All American GP LLC

Citizenship: USA

Amount Beneficially Owned: 12,000

Richard K. McGee

Address:  c/o Plains All American Pipeline, L.P., 333 Clay Street, Suite 1600, Houston, Texas 77002

Principal Occupation:  Vice President, General Counsel and Secretary of PNGS GP LLC and Executive Vice President, General Counsel and Secretary of Plains All American GP LLC

Citizenship:  USA

Amount Beneficially Owned:  20,000

John R. Rutherford

Address: c/o Plains All American Pipeline, L.P., 333 Clay Street, Suite 1600, Houston, Texas 77002

Principal Occupation: Executive Vice President of Plains All American GP LLC

Citizenship: USA

Amount Beneficially Owned: None

Al Swanson

Address: c/o Plains All American Pipeline, L.P., 333 Clay Street, Suite 1600, Houston, Texas 77002

Principal Occupation: Executive Vice President, Chief Financial Officer and Director of PNGS GP LLC and Executive Vice President and Chief Financial Officer of Plains All American GP LLC

Citizenship: USA

Amount Beneficially Owned: 50,844

(1)  Plains All American Pipeline, L.P. (“PAA”) does not directly have officers, directors or employees, rather its operations and activities are managed by Plains All American GP LLC (“GP LLC”), which employs PAA’s management and operational personnel. GP LLC is the general partner of Plains AAP, L.P. (“AAP LP”), which is the sole member of PAA GP LLC, which is PAA’s general partner. References to PAA’s officers are references to the officers of GP LLC.

13

W. David Duckett

Address: c/o Plains All American Pipeline, L.P., 333 Clay Street, Suite 1600, Houston, Texas 77002

Principal Occupation: President of Plains Midstream Canada ULC

Citizenship: Canada

Amount Beneficially Owned: 123,000

John P. vonBerg

Address: c/o Plains All American Pipeline, L.P., 333 Clay Street, Suite 1600, Houston, Texas 77002

Principal Occupation: Senior Vice President—Commercial Activities of Plains All American GP LLC

Citizenship: USA

Amount Beneficially Owned: 15,000

Chris Herbold

Address: c/o Plains All American Pipeline, L.P., 333 Clay Street, Suite 1600, Houston, Texas 77002

Principal Occupation: Vice President Accounting and Chief Accounting Officer of Plains All American GP LLC

Citizenship: USA

Amount Beneficially Owned: 1,500

Directors(1)

Greg L. Armstrong

Address: c/o Plains All American Pipeline, L.P., 333 Clay Street, Suite 1600, Houston, Texas 77002

Principal Occupation: Chairman of the Board, Chief Executive Officer and Director of PNGS GP LLC and of Plains All American GP LLC

Citizenship: USA

Amount Beneficially Owned: 162,000

Everardo Goyanes

Address: c/o Plains All American Pipeline, L.P., 333 Clay Street, Suite 1600, Houston, Texas 77002

Principal Occupation: Founder of Ex Cathedra LLC

Citizenship: USA

Amount Beneficially Owned: 35,000

Gary R. Petersen

Address: c/o Plains All American Pipeline, L.P., 333 Clay Street, Suite 1600, Houston, Texas 77002

Principal Occupation: Managing Partner of EnCap Investments L.P.

Citizenship: USA

Amount Beneficially Owned: 10,000

John Raymond

Address: c/o Plains All American Pipeline, L.P., 333 Clay Street, Suite 1600, Houston, Texas 77002

Principal Occupation: Owner and founder of The Energy & Minerals Group

Citizenship: USA

Amount Beneficially Owned: 624,997

(1)  PAA does not directly have officers, directors or employees, rather its operations and activities are managed by GP LLC, which employs PAA’s management and operational personnel. GP LLC is the general partner of AAP LP, which is the sole member of PAA GP LLC, which is PAA’s general partner. References to PAA’s directors are references to the directors of GP LLC.

14

Robert V. Sinnott

Address: c/o Plains All American Pipeline, L.P., 333 Clay Street, Suite 1600, Houston, Texas 77002

Principal Occupation: President, Chief Executive Officer, and Senior Managing Director of energy investments of Kayne Anderson Capital Advisors, L.P. and President of Kayne Anderson Investment Management, Inc., the general partner of Kayne Anderson Capital Advisors, L.P.

Citizenship: USA

Amount Beneficially Owned: 79,771

Vicky Sutil

Address: c/o Plains All American Pipeline, L.P., 333 Clay Street, Suite 1600, Houston, Texas 77002

Principal Occupation: Director, Corporate Development Midstream, and Director, Business Development Rockies, for Occidental Petroleum Corporation

Citizenship: USA

Amount Beneficially Owned: None

J. Taft Symonds

Address: c/o Plains All American Pipeline, L.P., 333 Clay Street, Suite 1600, Houston, Texas 77002

Principal Occupation: Chairman of the Board of Symonds Investment Company, Inc.

Citizenship: USA

Amount Beneficially Owned: 10,000

Christopher M. Temple

Address: c/o Plains All American Pipeline, L.P., 333 Clay Street, Suite 1600, Houston, Texas 77002

Principal Occupation: President of DelTex Capital LLC and Chairman of the Board of Texas Plastics Holdco, LLC

Citizenship: USA

Amount Beneficially Owned: None

15