Exhibit 3.1

CERTIFICATE OF AMENDMENT

TO

AMENDED AND RESTATED CERTIFICATE OF INCORPORATION

OF

NEW VALLEY CORPORATION

     New Valley Corporation, a corporation organized and existing under the laws of the State of Delaware (the “Corporation”), hereby certifies as follows:

     1. By unanimous written consent dated April 11, 2005, the Board of Directors of the Corporation adopted a resolution proposing and declaring advisable the following amendment to the Amended and Restated Certificate of Incorporation of the Corporation (the “Certificate of Incorporation”):

     RESOLVED, that it is advisable for the Corporation’s Certificate of Incorporation to be amended as follows:

The first paragraph of Article THIRD of the Certificate of Incorporation be amended to read in its entirety as follows:

THIRD: The aggregate number of shares which the Corporation shall have authority to issue shall consist of (i) 10,000,000 shares, par value $1.00 per share, designated as Class C Preferred Shares (the “Class C Preferred Shares”) and (ii) 50,000,000 shares, par value $.01 per share, designated as Common Shares (the “Common Shares”).

     2. The amendment of the Certificate of Incorporation effected by this Certificate was duly authorized at the Annual Meeting of Stockholders held on May 23, 2005, by the holders of a majority of the outstanding capital stock of the Corporation entitled to vote thereon, after first having been declared advisable by the Board of Directors of the Corporation, all in accordance with the provisions of Section 242 of the Delaware General Corporation Law.

     IN WITNESS WHEREOF, New Valley Corporation has caused this Certificate to be signed by Richard J. Lampen, its Executive Vice President, who hereby acknowledges under penalties of perjury that the facts herein stated are true and that this Certificate is the Corporation’s act and deed, this 23^rd day of May, 2005.

/s/ Richard J. Lampen  

Richard J. Lampen 

Executive Vice President 

2