Eoghan O’Connell made it a debut to remember as his goal five minutes from time, secured all three points on the road against a resilient Altrincham side.
Ollie Palmer put Wrexham ahead just after the hour mark, sliding the ball past Byrne after creating space from his first touch.
Miles Welch-Hayes made it all square in the 80th minute, after his low-drilled effort nestled into the bottom corner.
The game was won five minutes later, with substitute Sam Dalby being denied by Byrne and the post before debutant O’Connell slammed home.
Wrexham’s Phil Parkinson named three changes to the side that played out last weekend’s FA Cup tie against Sheffield United
The injuries to Jordan Tunnicliffe and Aaron Hayden handed new signing Eoghan O’Connell his debut, with Max Cleworth slotting in on the other side of Ben Tozer.
Reece Hall-Johnson the other change, with Anthony Forde, absent due to the birth of his new baby.
The first chance of the game fell to the hosts, as Welch-Hayes whipped a cross into the path of Jordan Hulme, but his header landed onto the roof of the net.
They came close on the 15-minute mark, as Sinclair played a clever header leaving Hulme one on one with Howard, but his lofted effort crashed against the crossbar.
Opportunities were hard to come by in the opening stages for Wrexham, but Luke Young managed the clearest chance inside the first twenty minutes, curling an effort over the crossbar.
The Red Dragons grew into the game and began to probe the Robins' defence, with Tom O’Connor testing Byrne from outside the area.
However, the hosts threatened again in the 35th minute, as Isaac Marriott bared down on goal, but Mark Howard was placed to make a comfortable save.
However, eight minutes before half time, Parkinson had more defensive concern as Reece Hall-Johnson was substituted after going down injured.
The final opportunity of the half fell to Altrincham in added time, as Cashman tried to curl his shot past Howard, but he misjudged the execution and his shot trickled wide.
They began the second period just as they ended the first as this time Cashman the supplier to Sinclair, dragged his shot well wide of Howard.
Wrexham got into their groove and started to trouble the Altrincham defence, with Paul Mullin shooting wide of Byrne’s goal, and Young seeing his effort deflected over.
In the 61st minute, Wrexham took the lead through Palmer as Elliot Lee’s sweeping cross found Palmer at the back post, who slotted past Bryne cooly.
Ten minutes from time the hosts equalised, as Welch Hayes drilled the ball past Howard, leaving the Wrexham keeper with no chance of stopping it.
The drama continued, and the pendulum swung back in the Red Dragons' favour, as Dalby was denied twice, and O’Connell slammed the ball home on debut to restore the lead.
Wrexham return to action on Tuesday night at Sheffield United in our Emirates FA Cup Fourth Round Replay.
Wrexham: Howard, Hall-Johnson (McAlinden 37’)( Dalby 84’), O’Connell, Tozer, Cleworth, McFadzean (Mendy 75’), Young ©, O’Connor, Lee, Mullin, Palmer
Subs not used: Lainton and J.Jones
Yellow card: O’Connor (3’), Young (42’)
Altrincham: Byrne, E.Jones, Baines, J.Jones, Welch-Hayes, Lundstrum, Marriott, Osborne ( Gyasi 75’), Cashman, Sinclair (Linney 68’), Hulme © (Kaja 68’)
Subs not used: Pringle and Oyedele
Yellow Card: Hulme
Attendance: 4865 (1650 Wrexham supporters)