The Brazilian notched the game's only goal 12 minutes after the interval to stun the hosts, who who had bossed proceedings in terms of possession.
Frank de Boer's side huffed and puffed in search of the equaliser they more than merited but were unable to find a way past Spartak goalkeeper Andrei Dikan despite a corner count of 13 to zero.
Dikan was called into his first action as early as the first minute, saving low at his near post from Siem de Jong's snap-shot, while teenage winger Lorenzo Ebecilio saw an effort blocked by Kirill Kombarov in the sixth minute and De Jong glanced a header over the bar soon after.
Another blast from the lively Ebecilio in the 12th minute, after cutting in from the left, needed tipping over the bar by Dikan, and the visiting stopper was then out quickly to smother at the feet of Demy De Zeeuw following Miralem Sulejmani's ball over the top.
De Zeeuw mustered a couple more sights of goal for himself but could find no way past Dikan, his first attempt kept out by the goalkeeper and he failed to make proper contact with the second when well placed.
Republic of Ireland forward Aiden McGeady caused the first minor worry for the Ajax defence in the 36th minute, his cross causing momentary panic in the box before goalkeeper Maarten Stekelenburg cleared.
Back at the other end, Sulejmani curled a 20-yard free-kick just wide with his left foot two minutes later and then swung in a corner from which Dikan kept out a powerful De Jong header as Ajax continued their fruitless pursuit of a first-half opener.
The pattern of the game remained the same for the opening 10 minutes of the second period, De Zeeuw launching himself to connect with Ebecilio's floated ball into the box only to head straight at Dikan.
Then, in the 57th minute, the visitors nicked what could prove a vital away goal against the run of play.
Alex got the better of a tussle with Daley Blind on the corner of the box before curling a left-footed shot past Stekelenburg to stun the home crowd.
De Jong had two decent opportunities to equalise within eight minutes, but failed to work the keeper. He first directed an effort wide from Sulejmani's corner - seemingly off his shoulder - and then shinned another attempt wide.
Ebecilio tried his luck from distance only to see Dikan keep it out with a strong left arm, with De Jong just unable to get to the rebound.
Spartak were at last offering something themselves going forward, and Stekelenburg had to be alert to prevent Kombarov's vicious low cross from sneaking in.
But Dikan remained the busier of the two goalkeepers.
Ebecilio made room for a left-footed shot in the 83rd minute which the Spartak stopper did well to beat away for a corner, and he then pulled off an even better save in stoppage time - flying to his left to tip Christian Eriksen's curling shot out for a corner which came to nothing.
Ajax 0-1 Spartak Moscow: Match Report - view commentary, squad, and statictics of the game as it happened.