Exhibit 5.1

September 22, 2014

The Board of Directors

Columbia Banking System, Inc.

1310 A Street

Tacoma, WA 98402-4200

Re: Legal Opinion Regarding Validity of Securities Offered

Ladies and Gentlemen:

We have acted as general corporate counsel to Columbia Banking System, Inc., a Washington corporation and bank holding company (“Columbia”), and are aware that Sullivan & Cromwell LLP has acted as special counsel to Columbia in connection with the registration under the Securities Act of 1933, as amended (the “Act”), of up to 4,342,949 shares of Columbia common stock, no par value per share (the “Common Shares”), to be issued in accordance with the Agreement and Plan of Merger dated as of July 23, 2014 (the “Merger Agreement”) by and between Columbia and Intermountain Community Bancorp.

In connection with the Common Shares that will be issued under the Merger Agreement, we have examined the following: (i) the Merger Agreement; (ii) the Registration Statement on Form S-4 filed by Columbia with the Securities and Exchange Commission (the “Registration Statement”); and (iii) such other documents as we have deemed necessary to form the opinion expressed below. As to various questions of fact material to such opinion, where relevant facts were not independently established, we have relied upon statements of officers of Columbia or representations and warranties of Columbia contained in the Merger Agreement. We have assumed, without independent investigation or review, the accuracy and completeness of the facts and representations and warranties contained in the documents listed above or otherwise made known to us.

Our opinion assumes that the Common Shares are issued in accordance with the terms of the Merger Agreement after the Registration Statement has become effective under the Act.

Based upon and relying solely upon the foregoing, we advise you that in our opinion, the Common Shares, or any portion thereof, when issued pursuant to the Merger Agreement, after the Registration Statement has become effective under the Act, will be validly issued under the laws of the State of Washington and will be fully paid and non-assessable.

This opinion letter is limited to the application of the laws of the State of Washington and the federal laws of the United States of America, and we express no opinion as to the laws of any other jurisdictions.

We hereby consent to the filing of this opinion as an exhibit to the Registration Statement and to the legal reference to this firm under the caption “Certain Legal Matters” as having passed upon the validity of the Common Shares. In giving such consent, we do not thereby admit that we are experts within the meaning of the Act.

Very truly yours,

Graham & Dunn PC

/s/ Graham & Dunn PC