Exhibit 5.1

[LETTERHEAD OF HINKLE, HENSLEY, SHANOR & MARTIN, LLP]

January 22, 2009

First State Bancorporation

7900 Jefferson N.E.

Albuquerque, New Mexico 87109

Re: First State Bancorporation

Registration Statement on Form S-3 (File No. 333-156517)

Ladies and Gentlemen:

We have acted as special New Mexico counsel to First State Bancorporation, a New Mexico corporation (the “Company”), in connection with the Registration Statement on Form S-3, as amended (the “Registration Statement”), initially filed by the Company on December 31, 2008 with the Securities and Exchange Commission (the “Commission”) under the Securities Act of 1933, as amended (the “Act”). The Registration Statement relates to the issuance and sale by the Company from time to time, pursuant to Rule 415 of the General Rules and Regulations of the Commission promulgated under the Act of the following securities of the Company: (i) an unspecified number of shares of the Company’s common stock, no par value (the “Common Stock”); (ii) an unspecified number of shares of the Company’s preferred stock, no par value (the “Preferred Stock”); (iii) fractional shares of the Company’s Preferred Stock represented by depositary shares evidenced by depositary receipts, which may be issued pursuant to one or more deposit agreements, proposed to be entered into between the Company and a bank or trust company to be named; (iv) senior debt securities, senior subordinated debt securities, subordinated debt securities and junior subordinated debt securities (collectively, the “Debt Securities”), which may be issued under an indenture, proposed to be entered into between the Company and a bank or trustee to be named; and (v) warrants to purchase Debt Securities or shares of Preferred Stock or Common Stock, which may be issued pursuant to one or more warrant agreements proposed to be entered into between the Company and a warrant agent or agents to be named. The Common Stock and the Preferred Stock are collectively referred to herein as the “Securities”. This opinion is being furnished in accordance with the requirements of Item 601(b)(5) of Regulation S-K under the Act.

In rendering the opinions set forth herein, we have examined and are familiar with originals, or copies certified or otherwise identified to our satisfaction, of:

a. The Registration Statement, as amended to the date hereof;

First State Bancorporation

January 22, 2009

Page 2

b. Restated Articles of Incorporation of the Company executed on October 25, 1996 and filed with the New Mexico State Corporation Commission on November 6, 1996, together with a Restated Certificate of Incorporation issued by the Office of the State Corporation Commission for the State of New Mexico;

c. The Articles of Amendment to the Articles of Incorporation for the Company, dated October 2, 1997, and filed with the New Mexico State Corporation Commission on October 3, 1997, together with the Certificate of Amendment dated October 3, 1997, and issued by the State Corporation Commission for the State of New Mexico;

d. Certificate of Amendment for the Company, issued by the Office of the Public Regulation Commission, dated July 17, 2006, and including Articles of Amendment to the Articles of Incorporation for the Company dated June 8, 2006;

e. Certificate of Amendment for the Company issued by the Office of the Public Regulation Commission, dated June 27, 2008, to which Articles of Incorporation, dated June 9, 2008, have been attached;

f. Certificate of Amendment for the Company, issued by the Office of the Public Regulation Commission dated July 18, 2008, to which Articles of Incorporation dated June 9, 2008, have been attached;

g. Amended Bylaws of the Company dated as of April 15, 2003, and certified as being in effect by the certificate of Marshall G. Martin, Secretary of the Company, dated January 14, 2009;

h. A copy of certain resolutions adopted by the Board of Directors of the Company on December 23, 2008, relating to the issuance of the Securities, the filing of the Registration Statement and related matters (the “Board Resolutions”), which resolutions were certified by Marshall G. Martin, Secretary of the Corporation, on January 14, 2009;

We have also examined originals or copies, certified or otherwise identified to our satisfaction, of such records of the Company and such agreements, certificates and receipts of public officials, certificates of officers or other representatives of the Company and others, and such documents, corporate records, and other instruments as we have deemed necessary or advisable for the purpose of rendering the opinions set forth below.

In our examination, we have assumed the legal capacity of all natural persons, the genuineness of all signatures, the authenticity of all documents submitted to us as originals, the conformity to original documents of all documents submitted to us as facsimile, electronic, certified or photostatic copies, and the authenticity of the originals of such copies. In making our examination of executed documents or documents to be executed, we have assumed that the parties thereto, other than the Company, had or will have the power, corporate or other, to enter into and perform all obligations thereunder and have also assumed the due authorization by all requisite action, corporate or other, and the execution and delivery by such parties of such documents and the validity and

First State Bancorporation

January 22, 2009

Page 3

binding effect thereof on such parties. As to any facts material to the opinions expressed herein that we did not independently establish or verify, we have relied upon oral or written statements and representations of officers and other representatives of the Company and others. Our opinions set forth herein are limited to those laws of the State of New Mexico. We do not express any opinion with respect to the laws of any jurisdiction other than the laws of the State of New Mexico.

Based upon the foregoing and subject to the limitations, qualifications, exceptions and assumptions set forth herein, we are of the opinion that:

1. With respect to the shares of Common Stock (the “Offered Common Stock”), when (i) if the Offered Common Stock is to be sold pursuant to a firm commitment underwritten offering, an underwriting agreement with respect to the Offered Common Stock has been duly authorized, executed and delivered by the Company and the other parties thereto; (ii) the Board of Directors of the Company or an authorized committee thereof has taken all necessary corporate action to authorize the issuance and sale of the Offered Common Stock in accordance with the Board Resolutions, including a determination of adequate consideration for the Offered Common Stock; (iii) certificates representing the shares of the Offered Common Stock have been manually signed by an authorized officer of the transfer agent and registrar for the Common Stock and registered by such transfer agent and registrar, and delivered to the purchasers thereof; and (iv) the Company receives consideration per share of the Offered Common Stock in an amount at least equal to the amount specified in the authorization mentioned in subsection(ii) above, and in a form legally valid under the laws of the State of New Mexico, the issuance and sale of the shares of Offered Common Stock (including any Offered Common Stock duly issued upon exchange or conversion of any shares of Preferred Stock that are exchangeable or convertible into Common Stock) will have been duly authorized, and such Offered Common Stock will be validly issued, fully paid and non-assessable.

2. With respect to the shares of any series of Preferred Stock (the “Offered Preferred Stock”), when (i) if the Offered Preferred Stock is to be sold pursuant to a firm commitment underwritten offering, an underwriting agreement with respect to the Offered Preferred Stock has been duly authorized, executed and delivered by the Company and the other parties thereto; (ii) the Board of Directors of the Company or an authorized committee thereof has taken all necessary corporate action to fix and determine the terms of the Offered Preferred Stock in accordance with the Board Resolutions, including the adoption of a certificate of designation for such Preferred Stock in the form required by applicable law and a determination as to the amount of consideration to be paid for such Offered Preferred Stock; (iii) such certificate of designation has been duly filed with the Public Regulation Commission for the State of New Mexico; (iv) certificates representing the shares of the Offered Preferred Stock have been manually signed by an authorized officer of the transfer agent and registrar for the Offered Preferred Stock and registered by such transfer agent and registrar, and delivered to the purchasers thereof; and (v) the Company receives the agreed upon consideration per share for the Offered Preferred Stock in an amount at least equal to the amount specified in the

First State Bancorporation

January 22, 2009

Page 4

authorization mentioned in subsection (ii) above, and in a form legally valid under the laws of the State of New Mexico, the issuance and sale of the shares of Offered Preferred Stock will have been duly authorized, and such shares will be validly issued, fully paid and non-assessable.

The opinions rendered herein are subject to the following qualifications and limitations:

a. We have assumed that, at the time shares constituting the Offered Common Stock are sold, the total number of shares of common stock of the Company which are then issued and outstanding, plus the number of shares of Offered Common Stock which are sold, will not exceed, in the aggregate, the number of shares of common stock authorized by the Company’s Articles of Incorporation as such Articles of Incorporation may be amended and in effect at the time of sale.

b. We have assumed that, at the time the shares constituting the Offered Preferred Stock are sold, the total number of shares of preferred stock of the Company which are then issued and outstanding, plus the number of shares of Offered Preferred Stock which are sold, will not exceed, in the aggregate, the number of shares of preferred stock authorized by the Company’s Articles of Incorporation, as such Articles of Incorporation may be amended and in effect at the time of sale.

We hereby consent to the filing of this opinion with the Commission as an exhibit to the Registration Statement. We also hereby consent to the reference to our firm under the caption “Legal Matters” in the Registration Statement.

Very truly yours,

/s/ Hinkle, Hensley, Shanor & Martin, LLP