The Tottenham loanee fired home with 15 minutes to go to secure the Lions their first win in four games and keep them in the play-off mix in the Championship.
Dany N'Guessan powered Kenny Jackett's men into a first-half lead before Jon Stead steered a first-time shot beyond David Forde, but City were level for just 12 minutes before Smith's match-winning volley.
Millwall started brightly as they looked to bounce back from Saturday's defeat at Cardiff, Darius Henderson heading wide from inside the box after just 56 seconds following a cross from Liam Feeney.
City goalkeeper Tom Heaton was tested for the first time in the 16th minute, Liam Trotter's effort from the left-hand side of the box being parried by the former Manchester United player.
But Heaton could do nothing about the home side's opener three minutes later, N'Guessan cracking a left-footed shot just out of reach of the 26-year-old to give Millwall a deserved lead with his first of the season.
The Lions then missed a great chance to open up a comfortable lead against a side they had failed to beat in the last four League games when Mark Beevers headed just wide of the post from James Henry's corner.
And only a last-ditch tackle from Shittu denied Martyn Woolford just as he was preparing to pull the trigger.
As the game hit the hour mark the visitors upped the tempo, Woolford shooting wide and then Sam Baldock's 25-yard strike forced David Forde into a fine stop.
It was no surprise when Stead delighted the 394 travelling fans with a leveller in the 63rd minute. Albert Adomah's long ball found the former Blackburn striker unmarked in front of goal and he guided the ball home.
Millwall's response was immediate with Heaton making two fine saves to deny Trotter and then Smith from putting the Lions back infront.
Smith may have been denied from 20 yards by Forde but he was on the scoresheet with a thumping volley in the 75th minute after Henry's free-kick was knocked down into his path.
Trotter almost secured the points with four minutes to go from long range but Heaton made another fine save and at the other end Forde denied Adomah.