Stephen had been preparing for this fight since his victory over the Hungarians at Baia in 1467. He knew the Ottomans would come eventually. When Sultan Mehmed II dispatched Hadim Suleiman Pasha, the governor of Rumelia, with an army that sources estimate between 30,000 and 120,000 troops, Stephen implemented a strategy of deliberate devastation. He ordered a scorched-earth campaign across southern Moldavia, burning crops, driving livestock north into the mountains, and evacuating the civilian population from the invasion corridor. Wells and water sources along the Ottoman line of march were poisoned. Specialist troops trained in ambush warfare harassed the advancing column, picking off foragers and stragglers, disrupting supply lines, and forcing the Ottomans to fight for every mile of muddy, frozen ground. By the time Suleiman Pasha's army reached the valley near Vaslui, it was exhausted, hungry, and strung out across unfamiliar terrain.

Stephen chose his ground with care. The area around Podul Inalt was marshy, hemmed in by forest, with the river crossing creating a natural bottleneck. The Moldavian army, roughly 40,000 strong and reinforced by smaller contingents of Hungarian and Polish allies, waited in concealed positions. Stephen arranged his forces so that the Ottomans would have to cross the bridge and advance into a narrowing valley where their superior numbers could not be deployed effectively. When the Ottoman vanguard committed to the crossing on the morning of January 10, the Moldavians struck. The battle unfolded in fog and winter cold, conditions that further disoriented the Ottomans, who could not see the extent of the forces arrayed against them. Stephen reportedly used war trumpets sounded from different positions in the forest to create the impression of encirclement, amplifying the confusion.

The Ottoman defeat was catastrophic. Venetian and Polish accounts put the Ottoman dead at between 40,000 and 100,000, figures that may include camp followers and non-combatants but nonetheless reflect an annihilation. The Crimean Khan who had joined the Ottoman campaign wrote to Mehmed II that he had lost his son and two brothers in the battle and had returned with only one horse. Stephen sent letters to the courts of Europe, including Pope Sixtus IV and the rulers of Hungary, Poland, and Venice, urging them to form a coalition against the Ottomans while Mehmed's best troops lay dead in a Moldavian swamp. The pope responded by naming Stephen Athleta Christi, Champion of Christ, a title that placed the Moldavian prince alongside the great defenders of Christendom. But the coalition Stephen sought never materialized. Europe praised his victory and did nothing to follow it up.

The Ottoman response came eighteen months later. In July 1476, Mehmed sent a second, larger army that defeated Stephen at the Battle of Valea Alba. But even in defeat, Moldavia held. The Ottomans failed to take the fortress at Suceava or the citadel at Neamt. Stephen reassembled his forces, invaded Wallachia with allies from Transylvania, and installed Vlad Tepes, Dracula himself, on the Wallachian throne, though Vlad's second reign lasted only weeks before Janissaries killed him near Bucharest. Between 1488 and 1490, Stephen built the Voronet Monastery to commemorate the victory at Vaslui. Its exterior walls were painted in 1547 with scenes of the Last Judgment against a background of cerulean blue so vivid that art historians speak of Voronet blue the way they speak of Titian red. Today the monastery stands on UNESCO's World Heritage List, a monument not only to faith but to a battle fought in fog on a frozen January morning.