SAN JOSE, Calif. -- Goalie Thomas Greiss earned a win against his former team. Captain John Tavares sparked a slumbering offense with two goals, and the New York Islanders won in a tough road building for the first time in nearly 13 years.

All in all, it was a good start to a three-game Western road swing.

Greiss stopped 34 of 36 shots as the Islanders beat San Jose 4-2 Tuesday, sending the reeling Sharks under .500 for the first time this season after a 4-0-0 start.

"We deserved it," New York coach Jack Capuano said. "We worked hard, we did a lot of good things against a really good hockey team. We haven't had puck luck in a while, especially the last couple games. I thought we played extremely well."

New York won in San Jose for the first time since Feb. 19, 2003. The Sharks had five wins and a tie as hosts against the Islanders since.

The Sharks (7-8-0) now face a daunting six-game trip to open a pivotal early-season stretch in which 14 of their next 19 games are on the road.

"We've got to come out harder to break it, whether that's even scoring right away or taking the play to them," said San Jose backup goalie Alex Stalock, who provided relief for starter Martin Jones but also let in a backbreaking soft goal. "That's something we stress, everybody knows that. It's just a matter of changing it."

The Islanders (8-5-3) scored a vital goal 45 seconds into the final period to squelch the momentum San Jose built in a strong middle period. New York defenseman Johnny Boychuk beat Stalock with a rising drive two strides outside the blue line.

"I thought it was going to hit my pad," Stalock said. "It's a bad feeling when you have no sensation of the puck."

Boychuk's third goal of the season put New York on top 3-1.

Defenseman Brent Burns pulled San Jose within one goal with his fifth of the season at 14:49. San Jose pressed hard with an extra attacker in the final minutes, but Tavares iced it with his second goal of the game into an empty net inside the last five seconds.

"We've obviously been having a tough time scoring, especially five-on-five," Tavares said. "We could sense we were ready today. The guys wanted to start the road trip off right. It wasn't the best second half, but we did some good things, and when you get two goals early, especially on the road, it gives you a lot of jump, a lot of confidence."

A goal from San Jose right winger Joel Ward midway through the middle period lit a fire, but the Sharks couldn't earn the equalizer after dominating zone play and quality chances the remainder of the second period.

"We're going to keep fighting," Sharks captain Joe Pavelski said. "We're in games that are coming right down to the wire, (and) we're usually down a goal right now. Guys are working, just like tonight, we get back to within one. We want to play with the lead."

It was a disastrous start for the Sharks, who trailed 2-0 just 3:30 after the opening faceoff. The Islanders took advantage of a bad line change to break in four-on-three on the opening shift of the game. Tavares was alone for a weakside tap-in 36 seconds into the game after Jones left a rebound of left winger Brock Nelson's shot.

"Brock just got a puck to the net, and I was just going there," Tavares said. "It seemed to be all open ice. When I got it, it was spinning pretty hard. I just got it past Jones. Just was able to sneak it in. It was nice to get it."

Mikhail Grabovski then used Burns as a screen during a one-on-two rush, and the New York center's 50-foot shot tipped off the bottom of Jones' left catching glove and into the net to quiet the home crowd and signal a call to Stalock.

"We needed a momentum change," Jones said. "Al stepped in and played great the last couple games. It's not fun getting pulled, but I don't know if I was surprised."

Sharks coach Peter DeBoer added, "You can give up a bad goal in this league and recover, but you can't give up two bad goals and expect to win. I think that was the case."

Stalock stopped 20 of the 21 shots he faced.

NOTES: San Jose coach Peter DeBoer was added as assistant to Edmonton coach Todd McLellan's North American entry into the 2016 World Cup. ... D Adam Pelech was recalled from Bridgeport of the AHL to give the Islanders insurance on the blue line. LW Taylor Beck and Pelech were healthy scratches. ... RW Melker Karlsson made his season debut for San Jose. Karlsson battled a lower-body injury early this season. ... New York's three-game West Coast swing concludes with games on consecutive nights in Los Angeles on Thursday and at Anaheim on Friday. ... The Sharks recalled LW Nikolay Goldobin and D Mirco Mueller from their AHL San Jose affiliate. Both were healthy scratches along with C Ben Smith, who is battling a head injury. ... The Sharks embark on a season-long six-game trip with games back-to-back on Saturday and Sunday in Detroit and Buffalo, respectively.