Nakata's 82nd minute pin point free-kick and Nolan's injury time strike were enough for Sam Allardyce's team to register a victory.
Fine saves from Baggies keeper Chris Kirkland looked to have at one stage spared his side's blushes. Kirkland denied Nolan with an acrobatic fingertip save early in the first half and also produced a brilliant point-blank block to deny Henrik Pedersen.
However, West Brom will rue Diomansy Kamara's first-half penalty miss. The striker scored from the first attempt, but after referee Mike Dean ruled the effort out for West Brom players running into the box before the kick had been taken, Kamara ballooned the retake over the bar.
Bolton started the brighter and through Nakata nearly took the lead after 15 minutes. He crossed from the right and Kevin Davies nipped in front of the visitors' defence but Kirkland made an excellent reflex save.
A minute later Greek ace Stelios Giannakopoulos found time and space in the box, but directed a header inches wide of the post.
But the game swung in West Brom's favour when they were awarded a penalty in the 19th minute. El Hadji Diouf was penalised for a clumsy challenge in the area and Kamara was given the chance to score from the spot.
The decision looked harsh, but Kamara coolly slotted home, only to miss the second attempt after his initial effort was ruled out.
Bolton continued to press and Nakata could not believe his bad luck when his close-range effort hit the back of Neil Clement's head and off the goal-line to safety.
At the other end a Paul Robinson cross was nearly directed into the net by Curtis Davies, but he only succeeded in glancing the ball wide of post.
Two minutes before the break Giannakopoulos found Nolan inside the box, but his powerful header was brilliantly tipped over the bar by Kirkland. The home side had one last chance before the interval to take the lead, but Giannakopoulos' curling free-kick, after Diouf had been felled on the edge of the box, flew inches over.
Nakata had Bolton's first chance of the second half, but his ambitious volley in the 55th minute flew well over. Bolton should have scored on the hour mark - but Kirkland again saved the Baggies' blushes. The in-form shot stopper made a superb save from Pedersen and from the rebound Diouf somehow failed to hit the target.
West Brom had their backs against the wall, but still managed to craft out a chance to score against the run of play. Kamara lost his marker at the back post, but keeper Jussi Jaaskelainen made a great block from close range to deny him.
Joey O'Brien fired over the bar in the 69th minute as Bolton continued to press for a deserved goal. Nolan saw a long-range free-kick also just miss the woodwork in the 75th minute, before a minute later striking a shot across the face of goal.
Cue Nakata. His carefully crafted free-kick was just too good for Kirkland and then Nolan rubbed salt into the wounds with his injury time strike which deservedly doubled the scoreline for Allardyce's high-fliers.