GUARANTEE AGREEMENT

Exhibit 10.16

GUARANTEE AGREEMENT

between

NORTH STATE BANCORP,

As Guarantor,

and

WELLS FARGO BANK, N.A.,

As Guarantee Trustee

Dated as of November 28, 2007

NORTH STATE STATUTORY TRUST III

Guar- TRUPs

TABLE OF CONTENTS

i

Guar- TRUPs

ii

Guar- TRUPs

G UARANTEE A GREEMENT , dated as of November 28, 2007, executed and delivered by N ORTH S TATE B ANCORP , a North Carolina corporation (the “Guarantor” ) having its principal office at 4270 The Circle at North Hills, Raleigh, North Carolina 27609, and W ELLS F ARGO B ANK , N.A., a national banking association, as trustee (in such capacity, the “Guarantee Trustee” ), for the benefit of the Holders (as defined herein) from time to time of the Preferred Securities (as defined herein) of North State Statutory Trust III, a Delaware statutory trust (the “Issuer” ).

W ITNESSETH :

W HEREAS , pursuant to an Amended and Restated Trust Agreement, dated as of the date hereof (the “Trust Agreement” ), among the Guarantor, as Depositor, the Property Trustee, the Delaware Trustee and the Administrative Trustees named therein and the holders from time to time of the Preferred Securities (as hereinafter defined), the Issuer is issuing $5,000,000 aggregate Liquidation Amount (as defined in the Trust Agreement) of its Floating Rate Preferred Securities (Liquidation Amount $1,000 per preferred security) (the “Preferred Securities” ) representing preferred undivided beneficial interests in the assets of the Issuer and having the terms set forth in the Trust Agreement;

W HEREAS , the Preferred Securities will be issued by the Issuer and the proceeds thereof, together with the proceeds from the issuance of the Issuer’s Common Securities (as defined below), will be used to purchase the Notes (as defined in the Trust Agreement) of the Guarantor; and

W HEREAS , as incentive for the Holders to purchase Preferred Securities the Guarantor desires irrevocably and unconditionally to agree, to the extent set forth herein, to pay to the Holders of the Preferred Securities the Guarantee Payments (as defined herein) and to make certain other payments on the terms and conditions set forth herein.

N OW , T HEREFORE , in consideration of the purchase by each Holder of Preferred Securities, which purchase the Guarantor hereby agrees shall benefit the Guarantor, the Guarantor executes and delivers this Guarantee Agreement to provide as follows for the benefit of the Holders from time to time of the Preferred Securities:

Guar- TRUPs

ARTICLE I

I NTERPRETATION AND D EFINITIONS

SECTION 1.1 Interpretation .

In this Guarantee Agreement, unless the context otherwise requires:

(a) capitalized terms used in this Guarantee Agreement but not defined in the preamble hereto have the respective meanings assigned to them in Section 1.2 ;

(b) the words “include”, “includes” and “including” shall be deemed to be followed by the phrase “without limitation”;

(c) all references to “the Guarantee Agreement” or “this Guarantee Agreement” are to this Guarantee Agreement as modified, supplemented or amended from time to time;

(d) all references in this Guarantee Agreement to Articles and Sections are to Articles and Sections of this Guarantee Agreement unless otherwise specified;

(e) the words “hereby”, “herein”, “hereof” and “hereunder” and other words of similar import refer to this Guarantee Agreement as a whole and not to any particular Article, Section or other subdivision;

(f) a reference to the singular includes the plural and vice versa; and

(g) the masculine, feminine or neuter genders used herein shall include the masculine, feminine and neuter genders.

SECTION 1.2 Definitions .

As used in this Guarantee Agreement, the terms set forth below shall, unless the context otherwise requires, have the following meanings:

“Affiliate” of any specified Person means any other Person directly or indirectly controlling or controlled by or under direct or indirect common control with such specified Person; provided , that the Issuer shall not be deemed to be an Affiliate of the Guarantor. For the purposes of this definition, “control” when used with respect to any specified Person means the power to direct the management and policies of such Person, directly or indirectly, whether through the ownership of voting securities, by contract or otherwise; and the terms “controlling” and “controlled” have meanings correlative to the foregoing.

“Beneficiaries” means any Person to whom the Issuer is or hereafter becomes indebted or liable.

2

Guar- TRUPs

“Board of Directors” means either the board of directors of the Guarantor or any duly authorized committee of that board.

“Common Securities” means the securities representing common undivided beneficial interests in the assets of the Issuer.

“Debt” means with respect to any Person, whether recourse is to all or a portion of the assets of such Person, whether currently existing or hereafter incurred, and whether or not contingent and without duplication, (i) every obligation of such Person for money borrowed; (ii) every obligation of such Person evidenced by bonds, debentures, notes or other similar instruments, including obligations incurred in connection with the acquisition of property, assets or businesses; (iii) every reimbursement obligation of such Person with respect to letters of credit, bankers’ acceptances or similar facilities issued for the account of such Person; (iv) every obligation of such Person issued or assumed as the deferred purchase price of property or services (but excluding trade accounts payable arising in the ordinary course of business); (v) every capital lease obligation of such Person; (vi) all indebtedness of such Person, whether incurred on or prior to the date of this Guarantee Agreement or thereafter incurred, for claims in respect of derivative products, including interest rate, foreign exchange rate and commodity forward contracts, options, swaps and similar arrangements; (vii) every obligation of the type referred to in clauses (i) through (vi) of another Person and all dividends of another Person the payment of which, in either case, such Person has guaranteed or is responsible or liable for, directly or indirectly, as obligor or otherwise; and (viii) any renewals, extensions, refundings, amendments or modifications of any obligation of the type referred to in clauses (i) through (vii).

“Event of Default” means a default by the Guarantor on any of its payment or other obligations under this Guarantee Agreement; provided, that except with respect to a default in payment of any Guarantee Payments, the Guarantor shall have received notice of default from the Guarantee Trustee and shall not have cured such default within thirty (30) days after receipt of such notice.

“Guarantee Payments” means the following payments or distributions, without duplication, with respect to the Preferred Securities, to the extent not paid or made by or on behalf of the Issuer: (i) any accumulated and unpaid Distributions (as defined in the Trust Agreement) required to be paid on the Preferred Securities, to the extent the Issuer shall have funds on hand available therefor at such time, (ii) the Redemption Price (as defined in the Trust Agreement) with respect to any Preferred Securities to the extent the Issuer shall have funds on hand available therefor at such time, and (iii) upon a voluntary or involuntary termination, winding up or liquidation of the Issuer, unless Notes are distributed to the Holders, the lesser of (a) the aggregate of the Liquidation Amount of $1,000 per Preferred Security plus accumulated and unpaid Distributions on the Preferred Securities to the date of payment, to the extent that

3

Guar- TRUPs

the Issuer shall have funds available therefor at such time and (b) the amount of assets of the Issuer remaining available for distribution to Holders in liquidation of the Issuer after satisfaction of liabilities to creditors of the Issuer in accordance with applicable law (in either case, the “Liquidation Distribution” ).

“Guarantee Trustee” means Wells Fargo Bank, N.A. in its capacity as trustee hereunder, until a Successor Guarantee Trustee, as defined below, has been appointed and has accepted such appointment pursuant to the terms of this Guarantee Agreement, and thereafter means each such Successor Guarantee Trustee.

“Holder” means any holder, as registered on the books and records of the Issuer, of any Preferred Securities; provided , that, in determining whether the holders of the requisite percentage of Preferred Securities have given any request, notice, consent or waiver hereunder, “Holder” shall not include the Guarantor, the Guarantee Trustee or any Affiliate of the Guarantor or the Guarantee Trustee.

“Indenture” means the Junior Subordinated Indenture, dated as of the date hereof, as supplemented and amended, between the Guarantor and Wells Fargo Bank, N.A., as trustee.

“List of Holders” has the meaning specified in Section 2.1.

“Majority in Liquidation Amount of the Preferred Securities” means a vote by the Holder(s), voting separately as a class, of more than fifty percent (50%) of the aggregate Liquidation Amount of all then outstanding Preferred Securities issued by the Issuer.

“Obligations” means any costs, expenses or liabilities (but not including liabilities related to taxes) of the Issuer, other than obligations of the Issuer to pay to holders of any Trust Securities the amounts due such holders pursuant to the terms of the Trust Securities.

“Officers’ Certificate” means, with respect to any Person, a certificate signed by the Chief Executive Officer, Chief Financial Officer, President or a Vice President of such Person, and by the Chief Credit Officer, Treasurer, an Assistant Treasurer, the Secretary or an Assistant Secretary of such Person, and delivered to the Guarantee Trustee. Any Officers’ Certificate delivered with respect to compliance with a condition or covenant provided for in this Guarantee Agreement (other than the certificate provided pursuant to Section 2.4 ) shall include:

(a) a statement that each officer signing the Officers’ Certificate has read the covenant or condition and the definitions relating thereto;

(b) a brief statement of the nature and scope of the examination or investigation undertaken by each officer in rendering the Officers’ Certificate;

4

Guar- TRUPs

(c) a statement that each officer has made such examination or investigation as, in such officer’s opinion, is necessary to enable such officer to express an informed opinion as to whether or not such covenant or condition has been complied with; and

(d) a statement as to whether, in the opinion of each officer, such condition or covenant has been complied with.

“Person” means a legal person, including any individual, corporation, estate, partnership, joint venture, association, joint stock company, limited liability company, trust, unincorporated association, government or any agency or political subdivision thereof or any other entity of whatever nature.

“Responsible Officer” means, with respect to the Guarantee Trustee, any Senior Vice President, any Vice President, any Assistant Vice President, the Secretary, any Assistant Secretary, the Treasurer, any Assistant Treasurer, any Financial Services Officer or Assistant Financial Services Officer or any other officer in the Corporate Trust Office of the Guarantee Trustee with direct responsibility for the administration of this Guarantee Agreement and also means, with respect to a particular corporate trust matter, any other officer to whom such matter is referred because of that officer’s knowledge of and familiarity with the particular subject.

“Senior Debt” means the principal of and any premium and interest on (including interest accruing on or after the filing of any petition in bankruptcy or for reorganization relating to the Guarantor whether or not such claim for post-petition interest is allowed in such proceeding) all Debt of the Guarantor, whether incurred on or prior to the date of the Indenture or thereafter incurred, unless it is provided in the instrument creating or evidencing the same or pursuant to which the same is outstanding, that such obligations are not superior in right of payment to the Preferred Securities; provided, however , that if the Guarantor is subject to the regulation and supervision of an “appropriate Federal banking agency” within the meaning of 12 U.S.C. 1813(q), the Guarantor shall have received the approval of such appropriate Federal banking agency prior to issuing any such obligation if not otherwise generally approved; provided further , that Senior Debt shall not include any other debt securities, and guarantees in respect of such debt securities, issued to any trust other than the Issuer (or a trustee of such trust), partnership or other entity affiliated with the Guarantor that is a financing vehicle of the Guarantor (a “financing entity”), in connection with the issuance by such financing entity of equity securities or other securities that are treated as equity capital for regulatory capital purposes guaranteed by the Guarantor pursuant to an instrument that ranks pari passu with or junior in right of payment to this Guarantee Agreement, including, without limitation, debt securities issued to North State Statutory Trust I and North State Statutory Trust II.

“Successor Guarantee Trustee” means a successor Guarantee Trustee possessing the qualifications to act as Guarantee Trustee under Section 4.1.

5

Guar- TRUPs

“Trust Indenture Act” means the Trust Indenture Act of 1939, as amended and as in effect on the date of this Guarantee Agreement.

Capitalized or otherwise defined terms used but not otherwise defined herein shall have the meanings assigned to such terms in the Trust Agreement as in effect on the date hereof.

ARTICLE II

R EPORTS

SECTION 2.1 List of Holders .

The Guarantor shall furnish or cause to be furnished to the Guarantee Trustee at such times as the Guarantee Trustee may request in writing, within thirty (30) days after the receipt by the Guarantor of any such request, a list, in such form as the Guarantee Trustee may reasonably require, of the names and addresses of the Holders (the “List of Holders” ) as of a date not more than fifteen (15) days prior to the time such list is furnished, in each case to the extent such information is in the possession or control of the Guarantor and is not identical to a previously supplied list of Holders or has not otherwise been received by the Guarantee Trustee in its capacity as such. The Guarantee Trustee may destroy any List of Holders previously given to it on receipt of a new List of Holders.

SECTION 2.2 Periodic Reports to the Guarantee Trustee .

The Guarantor shall deliver to the Guarantee Trustee, within one hundred and twenty (120) days after the end of each fiscal year of the Guarantor ending after the date of this Guarantee Agreement, an Officers’ Certificate covering the preceding fiscal year, stating whether or not to the knowledge of the signers thereof the Guarantor is in default in the performance or observance of any of the terms or provisions or any of the conditions of this Guarantee Agreement (without regard to any period of grace or requirement of notice provided hereunder) and, if the Guarantor shall be in default thereof, specifying all such defaults and the nature and status thereof of which they have knowledge.

SECTION 2.3 Event of Default; Waiver .

The Holders of a Majority in Liquidation Amount of the Preferred Securities may, on behalf of the Holders, waive any past Event of Default and its consequences. Upon such waiver, any such Event of Default shall cease to exist, and any Event of Default arising therefrom shall be deemed to have been cured, for every purpose of this Guarantee Agreement, but no such waiver shall extend to any subsequent or other default or Event of Default or impair any right consequent therefrom.

6

Guar- TRUPs

SECTION 2.4 Event of Default; Notice .

(a) The Guarantee Trustee shall, within ninety (90) days after the occurrence of a default, transmit to the Holders notices of all defaults actually known to the Guarantee Trustee, unless such defaults have been cured or waived before the giving of such notice, provided , that, except in the case of a default in the payment of a Guarantee Payment, the Guarantee Trustee shall be protected in withholding such notice if and so long as the Board of Directors, the executive committee or a trust committee of directors and/or Responsible Officers of the Guarantee Trustee in good faith determine that the withholding of such notice is in the interests of the Holders. For the purpose of this Section 2.4 , the term “default” means any event that is, or after notice or lapse of time or both would become, an Event of Default.

(b) The Guarantee Trustee shall not be deemed to have knowledge of any default or Event of Default unless the Guarantee Trustee shall have received written notice, or a Responsible Officer charged with the administration of this Guarantee Agreement shall have received written notice, of such default or Event of Default from the Guarantor or a Holder.

ARTICLE III

P OWERS , D UTIES A ND R IGHTS O F T HE G UARANTEE T RUSTEE

SECTION 3.1 Powers and Duties of the Guarantee Trustee .

(a) This Guarantee Agreement shall be held by the Guarantee Trustee for the benefit of the Holders, and the Guarantee Trustee shall not transfer this Guarantee Agreement to any Person except a Holder exercising its rights pursuant to Section 5.4(d) or to a Successor Guarantee Trustee upon acceptance by such Successor Guarantee Trustee of its appointment to act as Successor Guarantee Trustee. The right, title and interest of the Guarantee Trustee shall automatically vest in any Successor Guarantee Trustee, upon acceptance by such Successor Guarantee Trustee of its appointment hereunder, and such vesting and cessation of title shall be effective whether or not conveyancing documents have been executed and delivered pursuant to the appointment of such Successor Guarantee Trustee.

(b) The rights, immunities, duties and responsibilities of the Guarantee Trustee shall be as provided by this Guarantee Agreement and there shall be no other duties or obligations, express or implied, of the Guarantee Trustee. Notwithstanding t