The highway runs from Merrick Road (unsigned County Route 27 or CR 27) in Seaford to NY 25 in Syosset.

The origins of the expressway date back to 1954 when engineering pioneer Robert Moses proposed that a highway be built between Wantagh and Oyster Bay.

The Seaford–Oyster Bay Expressway northbound lanes begins at the on-ramp from Merrick Road (unsigned CR 27) near the outer limits of downtown Seaford in southeastern Nassau County.

There is an aging sign at the southern terminus, depicting the highway as "NY 135" and showing the nearest control city as Oyster Bay.

[4] The expressway progresses northward from the on-ramp, crossing over Waverly Avenue and passing the first guide sign for exit 2 (NY 27), about 0.5 miles (0.8 km) ahead from this point.

After a short distance, Seamans Neck Road (CR 191) passes exit 3 for NY 105 and continues west of the expressway going north to Plainedge.

From there, the expressway turns to the north and begins to parallel the Bethpage Parkway as it meets NY 24 (Hempstead Turnpike).

[8] Under Robert Moses' original plans for the highway, the northern terminus of the expressway would be placed near brand new local ferry terminals in Oyster Bay.

From there, commuters could connect to the city of Stamford, Connecticut, 12 miles (19 km) to the north by way of ferries across Long Island Sound.

[9] The proposed highway was added to the New York State Highway Law as follows, with annotations in brackets:[10] ... Seaford–Oyster Bay expressway, beginning at a point on the Wantagh parkway in the vicinity of the hamlet of Wantagh, thence running generally through or near the hamlets of Seaford, Bethpage and Plainview to a point on state highway nine thousand twenty-one [NY 106] south of the village of Oyster Bay; ...[10] One of the major problems with the proposed alignment of the expressway was that it divided each community that it passed through.

Under his plan, it would now begin at the Ocean Parkway in Tobay Beach, cross Great South Bay and enter West Amityville at Clocks Boulevard.

From West Amityville, the expressway was to turn to the northeast near the current-day Sunrise Mall, and progress its way through Massapequa and Farmingdale into Bethpage State Park.

From there, it would veer to the northwest, approaching and intersecting with the Jericho Turnpike (NY 25) about 0.75-mile (1.21 km) from its current northern terminus.

[14] Construction continued rapidly, with the section from Old Country Road down to the Southern State Parkway (exit 4) being completed only a year later.

[2] From there, the construction slowed, with the final piece from Merrick Road (CR 27) to the Southern State Parkway opening to traffic in late 1969.

[3] In 1957, a plan for a bridge to Westchester County across Long Island Sound was first proposed by Charles H. Sells, a former commissioner for the New York State Department of Public Works.

The proposed bridge was to cost $150 million (1966 USD) and had the support of Governor Nelson Rockefeller and many officials on Long Island.

Faced with growing opposition, Governor Rockefeller cancelled the plans for the bridge on June 20, 1973, nine years after the first proposal by Moses.

Some were reconsidered during the 1990s, but the New York State Department of Transportation (NYSDOT) backed away from the idea in belief that it would not relieve congestion.

In 1973, the Tri-State Transportation Commission proposed restudying the idea of extending the expressway northward back to its originally-planned northern terminus, the hamlet of Oyster Bay, even though the bridge project was shelved.

To prevent the noticeable tunnel, the developer proposed building a park atop the entrance with ball fields, tennis courts, and several other amenities.

[13] By 1975, the Tri-State Transportation Commission proposed a plan to extend the highway south to the Wantagh State Parkway, which was NY 135's originally-planned southern terminus.

In the 2000s, NYSDOT repaired segments of NY 135, along with many other highways in Nassau and nearby Suffolk counties, where the concrete was beginning to wear out.

[30] At 9:30 a.m. on May 24, 1988, a tanker truck loaded with as much as 3,000 imperial gallons (14,000 L) of propane fuel overturned and exploded into flames along the expressway.

Nassau County police ordered the evacuation of 1,000 residents in the immediate area, along with nearby commuter routes, the Sunrise Highway and Long Island Rail Road's Montauk Branch.

The change was made both to avoid confusion with the Wantagh Parkway and to accommodate a request from the community of Seaford to popularize their town.

There have also been attempts to rename the expressway with dedications to various Presidents of the United States such as Theodore Roosevelt and Ronald Reagan.

The lane alignment was set up so that the proposed extension of the Bethpage State Parkway would have run within the median of NY 135.