About two years1
Shortly after the Thrawn novel was announced, Timothy Zahn was interview by StarWars.com, and he said that the events of the novel dovetailed into season 3 of Star Wars: Rebels (where Thrawn is a primary antagonist):
Q: Can you give us any hints about the story and what readers will learn in the new book?
Thrawn will span several years of the Star Wars timeline, beginning with his first encounter with the Empire and ending just before the opening of Rebels Season 3.
This is somewhat supported by the novel itself, which ends with Thrawn being promoted to his iconic rank:
The throne room was as Thrawn remembered it, though he saw it now with different eyes. The new uniform he'd been given was white, with gold shoulder bars and silver collar insignia, completely unlike anything else in the Imperial Navy. The rank insignia plaque the Emperor held in his gnarled hand was equally impressive: twelve tiles in blue, red, and gold.
The Emperor's face was as Thrawn had never seen it. His expression holds satisfaction, with hints of both amusement and malice. "Congratulations, Grand Admiral," he said as he held out the insignia plaque. "An excellent day for you. An excellent day for my Empire."
Thrawn Chapter 29
And his first appearance on Rebels has him note that his promotion was "recent":
Tarkin: Grand Admiral Thrawn.
Konstantine: "Grand Admiral"?
Thrawn: The Emperor recently promoted me after my victory at Batonn.
Star Wars: Rebels Season 3 Episode 1: "Steps into Shadow"
As Pablo Hidalgo confirmed on Twitter, the season 3 premiere of Rebels is about two years before A New Hope:
@pablohidalgo six months pass between the S2 finale and the S3 premiere. We're about 2 years from Ep4
Unfortunately, I'm not sure there's enough information given in the novel to construct an accurate timeline of events. There is some information, and I've made a few attempts, but the fact that the novel portrays two interweaving narratives has been throwing me off more than slightly. All I'm prepared to state with confidence right now is that Thrawn made contact with the Empire no later than 6 or 7 BBY.
1 I'm deliberately not counting the epilogue, which takes place in an ambiguous timeframe, possibly after Thrawn's death