Fulham captain Tom Cairney's 42nd-minute strike seemed set to give Fulham their first victory in five games in all competitions until Nuhiu struck in the fourth minute of five added on at Hillsborough.
It was richly deserved as Monk's side – he began his reign with a 2-0 victory at Huddersfield last weekend – had carved out the better chances throughout the 90 minutes.
Up until Cairney's strike, Fulham had dominated the game in terms of possession but had done little of note with it, save for a tame effort from Ivan Cavaleiro and a left-wing free-kick from Anthony Knockaert swung into the arms of Keiren Westwood.
Instead, it was the Owls who had come closest to breaking the deadlock, with Adam Reach a thorn in Fulham's right flank.
A delightful 10th-minute cross from Reach's left foot found Steven Fletcher, whose header was just over the angle of bar and post, while 11 minutes later a piercing low ball from the 26-year-old winger with his right foot just evaded the Scot.
In the 24th minute, Wednesday came close to making the breakthrough, with a first-time shot from Reach turned away by Marcus Bettinelli.
Although Owls captain Barry Bannan reacted quickly in pouncing on the loose ball, his attempt from a tight angle clipped a post.
After Bettinelli had saved a shot on the turn from 15 yards from Keiran Lee, with Reach again the supplier with a low ball from the right, Fulham struck three minutes before the break.
From Joe Bryan's low cross from the left, Westwood, perhaps deceived by the sun, which had been in his eyes throughout the first half despite him wearing a cap, took his time to react.
In the end, Westwood could only push the ball out to Cairney, who side-footed home his second goal of the season from 10 yards.
The second period was almost a mirror image of the first, with Fulham controlling possession, but Wednesday the team carving out the opportunities, and ultimately netting the goal.
On the hour the home side should have equalised, with Bannan placing a cross onto the head of Jacob Murphy, who could only glance his effort narrowly wide with his first touch of the game after replacing Reach a minute before.
After Bannan had volleyed a 20-yard left-footer just past a post two minutes later, the game had to wait until the 87th minute for the next chance, with 77th-minute substitute Nuhiu – on for Fletcher – heading a cross from Liam Palmer straight at Bettinelli.
That seemed to be it until one last attack at the death, with Nuhiu stabbing home at the far post after a deep cross from Kadeem Harris had taken a slight deflection into his path.