Exhibit 5.1

November 1, 2004

The Board of Directors

Columbia Banking System, Inc.

1301 “A” Street

Tacoma, WA 98402

Re:      Legal Opinion Regarding Validity of Securities Offered

Ladies and Gentlemen:

We have acted as counsel to you in connection with the preparation of a Registration Statement on Form S-8 (the “Registration Statement”) under the Securities Act of 1933, as amended (the “Act”), which you are filing with the Securities and Exchange Commission (the “Commission”) with respect to 161,452 shares of no par value common stock (the “Shares”), of Columbia Banking System, Inc., a Washington corporation (“Company”), authorized for issuance upon exercise of options granted under the Bank of Astoria Amended and Restated Nonemployee Director Stock Option Plan and the Bank of Astoria Amended and Restated Combined Incentive and Non-Qualified Stock Option Plan (collectively, the “Plans”) that were assumed by the Company as a result of the acquisition of Bank of Astoria.

In connection with the offering of the Shares, we have examined: (i) the Plans and related option agreements, listed as Exhibits 99.1 - 99.4 in the Registration Statement; (ii) the Registration Statement, including the remainder of the exhibits; and (iii) such other documents as we have deemed necessary to form the opinions hereinafter expressed. As to various questions of fact material to such opinions, where relevant facts were not independently established, we have relied upon statements of officers of the Company.

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

Based upon and subject to the foregoing, we are of the opinion that the Shares, or any portion of the Shares, have been duly authorized and that, upon registration of the Shares, issuance by the Company of and receipt of the consideration for the Shares, consistent with the terms of the Plans, the Shares will be validly issued, fully paid, and nonassessable.

We hereby consent to the filing of this opinion as Exhibit 5.1 to the Registration Statement. This consent shall not be construed to cause us to be in the category of persons whose consent is required to be filed pursuant to Section 7 of the Act or the rules and regulations of the Commission promulgated thereunder.

Very truly yours,

Graham & Dunn PC

/s/ Graham & Dunn PC