Yorkshire had been pipped to the 2013 County Championship by Durham; they had finished third in 2010, when a batting collapse on the final day of the season against Kent cost them the title; and they had lost the 2012 Twenty20 Cup final to Hampshire.
“I was starting to think, ‘Maybe this just isn’t meant to be’,” confessed Gale.
“I wondered if we’d ever win a trophy under my leadership.”
Three years on, and Gale has two Championship trophies under his belt after back-to-back wins in 2014 and 2015.
His side are overwhelming favourites to make it three-in-a-row this year.
In addition, this is Gale’s benefit year – a reward for more than a decade of loyal service.
If he can achieve the hat-trick in his benefit year, that would be a genuine cricketing fairytale.
“For us players to win it three times in a row would be phenomenal,” he admitted.
“When you walk around the ground at Headingley, all you see is history – pictures of the great players of the past – and you don’t really see the current players represented that much.
“We want to create our own history to the point that when we come into the ground in 10-15 years’ time, it’s our faces that people are seeing everywhere, and it’s our team that people are still talking about.
“If we can make it three-in-a-row, more and more people would look back and say, ‘You know what, those lads were good, they were a good side.’
“That’s my biggest driver going into the season.”
Not that Gale is counting his chickens.
Since 2013 in particular, when Durham overhauled his team right at the last, he has made a big thing about urging his players to focus on the processes required to achieve the end result as opposed to the end result itself, something he admits they are “probably sick of hearing”.
In other words, Gale asks them to concentrate on each day, each session and each ball in the belief that the rest will then take care of itself.
It does not mean, of course, that the players can somehow close their minds to the prospect of a hat-trick of titles, which would be impossible, but it does mean that Gale does not want them thinking about September when they are playing a match in the middle of April.
“September is so far away,” he said. “In professional sport, a week is a long time, and I’m not going to look too far ahead myself and try to guess which players we’re going to have available at any particular time, for example, and who the opposition are going to have.
“People always talk about taking it one game at a time, but it’s so true. You just can’t get ahead of yourself.
“You just have to give yourself the best chance by working hard.
“We know what works for us in the longer form now, and it’s just about replicating that on a day-to-day basis as many times as we can.
“If we do that, we’ll win games of cricket.”
It sounds simple, but it is anything but.
Keeping minds off the end goal will be even harder this year, for no club has achieved the hat-trick for nearly half-a-century.
Yorkshire, the last county to do it, are clearly the side to beat once more, and Gale insists they are there to be shot at.
Indeed, he says that he would demand that his own side raised their game if they were playing a team chasing a hat-trick of titles.
“It will be our hardest challenge,” he reflected.
“When you win it two years on the bounce, teams just up their game against you.
“I know that if we were playing against a team who’d won back-to-back Championships, I’d expect our lads to raise their game 10-20 per cent.
“We saw it a little bit last year, when people played a different brand of cricket against us at times and produced some flatter wickets.
“Teams will be trying to put one over on us.”
Gale believes that any of the nine clubs in this year’s top-flight could potentially win the title, including newly-promoted Surrey and Lancashire.
Eight of the nine counties that are Test match venues are now in Division One (the most since the introduction of two divisions in 2000), with Somerset the exception.
Only Glamorgan are marooned in Division Two.
Asked to identify possible contenders to Yorkshire this year, Gale said: “Warwickshire will be strong. They’ve got as strong a squad as I’ve seen.
“They have always been strong with their bowling but have struggled for runs at times.
“Now they have got (Ian) Bell and (Jonathan) Trott, possibly for most of the season if Bell doesn’t get back into the England set-up.
“You can probably pencil them in for 1,000 runs. They will be a good side.”
Gale went on: “Middlesex will probably get a lot of confidence from the way they played last year.
“They are an up-and-coming team who can take 20 wickets.
“And I don’t think you can ever write Durham off.
“They will have (Ben) Stokes and (Mark) Wood at the start of the season.
“If they are able to keep (Chris) Rushworth and (Graham) Onions fit, they have the mentality of a winning team.
“And you never know with Notts. They finished the season strong after a poor start. When Peter Moores came in, they turned it around.
“If they start as they finished, they could be up there.
“You could literally go down every team and go, ‘If they get out of the blocks well, they could win it’.”
Perhaps Gale’s biggest challenge will be managing expectations.
For all that there are a number of strong teams in Division One, there are none stronger than his own if Yorkshire can stay largely injury-free.
Even without their England players, Yorkshire have proved how strong they are in recent times.
And if any captain can lead his side to the hat-trick, it is Gale.