Exhibit 8.1

FORM OF OPINION

[LETTERHEAD OF WACHTELL, LIPTON, ROSEN & KATZ]

[ ], 2013

Provident New York Bancorp

400 Rella Blvd.

Montebello, New York 10901

Ladies and Gentlemen:

Reference is made to the Registration Statement on Form S-4 (as amended or supplemented through the date hereof, the “Registration Statement”) of Provident New York Bancorp, a Delaware corporation (“Provident”), including the Joint Proxy Statement forming a part thereof, relating to the merger of Sterling Bancorp, a New York corporation (“Sterling”), with and into Provident (the “Merger”) pursuant to the terms of the Agreement and Plan of Merger, dated as of April 3, 2013, by and between Sterling and Provident (as amended or supplemented through the date hereof, the “Agreement”).  At your request, and in connection with the filing of the Registration Statement, we are rendering our opinion concerning certain United States federal income tax consequences of the Merger.  Capitalized terms not defined herein have the meanings specified in the Agreement.

In providing our opinion, we have examined the Agreement, the Registration Statement, and such other documents as we have deemed necessary or appropriate for purposes of our opinion.  In addition, we have assumed that (i) the transaction will be consummated in accordance with the provisions of the Agreement and as described in the Registration Statement (and no transaction or condition described therein and affecting this opinion will be waived by any party), (ii) the statements concerning the transaction and the parties thereto set forth in the Agreement and in the Registration Statement are true, complete and correct, (iii) the factual statements and representations made by Provident and Sterling in their respective officer’s

certificates dated as of the date hereof and delivered to us for purposes of this opinion (the “Officer’s Certificates”) are true, complete and correct as of the date hereof and will remain true, complete and correct at all times up to and including the Effective Time, (iv) any such statements and representations made in the Officer’s Certificates “to the knowledge of” any person or similarly qualified are and will be true, complete and correct without such qualification, and (v) Provident, Sterling and their respective subsidiaries will treat the Merger for United States federal income tax purposes in a manner consistent with the opinion set forth below.  If any of the above described assumptions are untrue for any reason or if the transaction is consummated in a manner that is different from the manner described in the Agreement or the Registration Statement, our opinion as expressed below may be adversely affected.

Based upon and subject to the foregoing, we hereby confirm to you that, subject to the qualifications and limitations contained herein and therein, (i) the discussion under the caption “MATERIAL U.S. FEDERAL INCOME TAX CONSEQUENCES OF THE MERGER” constitutes our opinion as to the material U.S. federal income tax consequences of the Merger to holders of Sterling common stock, and (ii) it is our opinion that, for United States federal income tax purposes, the Merger will qualify as a “reorganization” within the meaning of Section 368(a) of the Code.

We express no opinion on any issue relating to the tax consequences of the transactions contemplated by the Registration Statement other than the opinion set forth above.  Our opinion is based on current provisions of the Internal Revenue Code of 1986, as amended, Treasury Regulations promulgated thereunder, published pronouncements of the Internal Revenue Service and case law, any of which may be changed at any time with retroactive effect.  Any change in applicable laws or the facts and circumstances surrounding the transaction, or any inaccuracy in the statements, facts, assumptions or representations upon which we have relied, may affect the continuing validity of our opinion as set forth herein.  We assume no responsibility to inform Provident of any such change or inaccuracy that may occur or come to our attention.

We are furnishing this opinion in connection with the filing of the Registration Statement and this opinion is not to be relied upon for any other purpose without our prior written consent.  We hereby consent to the filing of this opinion with the Securities and Exchange Commission as an exhibit to the Registration Statement, and to the references therein to us.  In giving such consent, we do not thereby admit that we are in the category of persons whose consent is required under Section 7 of the Securities Act of 1933, as amended.

Very truly yours,

2