Exhibit 23.5

CONSENT OF INDEPENDENT REGISTERED PUBLIC ACCOUNTING FIRM

We consent to the incorporation by reference in this Registration Statement on Form S-4 of Provident New York Bancorp of our report dated February 22, 2013 relating to the financial statements of Sterling Bancorp, and our report dated the same date relative to the effectiveness of internal control over financial reporting, appearing in the 2012 Annual Report on Form 10K of Sterling Bancorp and to the reference to us under the heading “Experts” in this Registration Statement.

/s/ Crowe Horwath LLP

Livingston, New Jersey

June 4, 2013