Exhibit 5

July 12, 2004

The Board of Directors

Columbia Banking System, Inc.

1310 A Street

Tacoma, Washington 98402-4200

Re:    Legal Opinion Regarding Validity of Securities Offered

Ladies and Gentlemen:

We have acted as counsel for Columbia Banking System, Inc., a Washington corporation and bank holding company (“Columbia”), in connection with the registration under the Securities Act of 1933, as amended (the “Act”) of up to 1,277,750 shares of Columbia common stock, no par value per share (the “Shares”), to be issued in accordance with the Plan and Agreement of Merger dated as of June 7, 2004 (the “Plan”) between Bank of Astoria and New Bank of Astoria, upon its formation by Columbia.

In connection with the Shares that will be issued under the Plan, we have examined the following: (i) the Plan; (ii) the Registration Statement on Form S-4 filed by Columbia with the Securities and Exchange Commission on July 12, 2004 (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 Plan. 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 Shares are issued in accordance with the terms of the Plan 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 Shares, or any portion thereof, when issued pursuant to the Plan, 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 nonassessessable.

Columbia Banking System, Inc.

July 12, 2004

Page 2

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 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/