Exhibit 23.6

CONSENT OF SANDLER O’NEILL & PARTNERS, L.P.

We hereby consent to the inclusion of our opinion letter, dated                     , 2004, to the Board of Directors of Bank of Astoria (the “Company”) as Appendix C to the Proxy Statement/Prospectus relating to the proposed merger of the Company with Columbia Banking System, Inc. (“Columbia”) contained in Pre-effective Amendment No.          to Columbia’s Registration Statement on Form S-4 as filed with the Securities and Exchange Commission on the date hereof, and to the references to our firm and such opinion in such Proxy Statement/Prospectus. In giving such consent, we do not admit that we come within the category of persons whose consent is required under Section 7 of the Securities Act of 1933, as amended (the “Act”), or the rules and regulations of the Securities and Exchange Commission thereunder (the “Regulations”), nor do we admit that we are experts with respect to any part of such Registration Statement within the meaning of the term “experts” as used in the Act or the Regulations.

                    , 2004