There were promotions, relegation battles and eventually the move away from Maine Road, but the players recruited along the way also helped establish the foundations for what followed.
Bernstein, who joined City's board in 1994 before becoming chairman in 1998, was involved in a period when recruitment required a mixture of judgement, opportunity and, occasionally, a little bit of luck.
Speaking exclusively to Football Presse, he revisits some of the less familiar stories behind City's signings, including an unexpected arrival from Liberia, the popularity of a Chinese international and a transfer that almost happened but could, in his opinion, have changed the club's immediate future.
George Weah was a glamorous signing rather than a cornerstone
Few arrivals at Maine Road attracted quite the same attention as George Weah. The former Ballon d'Or winner joined City in 2000, bringing an extraordinary reputation to a club that was still trying to establish itself in the Premier League.
For Bernstein, however, there was a clear understanding of what the Liberian could realistically offer at that stage of his career.
"Well, it happened. I mean, obviously one of the world's great, great players. He was obviously at the end of his career. We saw it as an opportunity to bring in someone who probably would not be a 90-minute player, you know, for every match at that stage of his career.
"But he had the talent and so on to work alongside the sort of Paulo Wanchope and Shaun Goater that we had. And it worked okay. But I can't say it was an outstanding success."
The signing provided City with a celebrated name, although Bernstein remembers the limitations as clearly as the excitement.
There was something particularly unusual about seeing a player of Weah's standing competing in English football's lower-profile fixtures.
"I remember early on, I think we played a match at Gillingham. I mean, can you imagine George Weah playing at Gillingham?"
Bernstein's assessment was ultimately that the move had been worthwhile, but not one of the defining pieces of City's recruitment strategy.
"He wasn't a core signing. No, he was a glamorous signing, but not one of the most important signings."
Sun Jihai brought something different to City
Another player who left an impression on Bernstein was Sun Jihai.
The Chinese defender arrived at City in 2002 from Dalian Shide, becoming an important figure during the club's return to the Premier League and subsequent development.
Unlike the Weah acquisition, Bernstein cannot recall the precise circumstances that brought Sun to Manchester. What stayed with him was the player's professionalism and the connection he established with supporters.
"I don't remember. It came through an agent. I can't quite remember, but he was great. And of course, he brought a lot of his local support behind him. He was great as well. I remember he was a really good guy and a really good professional.
"I enjoyed working with him, but I can't, to be honest, remember quite how we got him."
Sun's arrival was significant beyond his contribution on the pitch. He attracted considerable interest from the Chinese community and became an important figure in the club's growing international profile.
He would go on to make more than 130 appearances for City, spending six years at the club and becoming a popular member of the squad.
For Bernstein, however, the lasting memory was more straightforward: a thoroughly professional footballer who made a positive impression on those around him.
Shaun Goater became an unlikely Manchester City hero
Not every important signing arrives with a grand reputation or an expectation of transforming a football club.
Bernstein's recollection of Shaun Goater is a particularly good example of how a transfer can develop into something much bigger than initially anticipated.
The Bermudian striker joined City from Bristol City in 1998, and his arrival was anything but straightforward.
"Well, you take Shaun Goater, the Goat. You know, when he came in, I remember we signed him at the last minute before the transfer deadline. It was all like about a minute before, maybe even a minute after. I'm not sure!
"But we signed him and, you know, we had reasonable expectations. But he really was outstanding and he grew with the club and he was a great personality."
Goater became one of the most recognisable figures of City's recovery, scoring the goals that helped Joe Royle's team climb through the divisions.
His relationship with supporters became particularly special, with the famous 'Feed the Goat' chant reflecting the affection he generated at Maine Road.
Bernstein remembers that connection as being about much more than simply scoring goals.
"And all the stuff about 'Feed the Goat' and so on, the fans really, really loved him. And he's been a bit of an unlikely hero. But I think when people look back on that time, Shaun Goater will be one of the heroes with Paul Dickov and others, you know, who will stand the test of time."
It is a revealing recollection from a chairman who witnessed the club's revival at close quarters. Goater was not necessarily recruited with the expectation that he would become such an enduring symbol, but his performances and personality made him one of the defining players of that period.
Uwe Rösler made a lasting impression
Another forward Bernstein remembers particularly fondly is Uwe Rösler.
The German striker had already established himself as a popular figure at Maine Road before Bernstein's chairmanship, having arrived from 1. FC NĂŒrnberg in 1994.
His contribution was substantial, scoring 64 goals in 165 appearances for City. He also developed a particularly strong relationship with the supporters.
Bernstein's description of him is brief but affectionate.
"He was a very good player. I liked him. Dynamic, had personality. Down the middle, generally a good scorer of goals. Yeah, he did very well for us. I liked him very much."
Rösler's importance to the club was not simply measured by his goals. His commitment and personality made him a natural favourite among supporters during a difficult period in City's history.
For Bernstein, he represented the type of player who could give a team an identity and provide supporters with somebody they could genuinely connect with.
The transfer that might have saved Manchester City from relegation
Perhaps the most revealing recruitment story concerns a player City failed to sign.
Bernstein remembers Joe Royle's determination to bring Ugo Ehiogu to Maine Road. The powerful central defender was an established Premier League player with Aston Villa, but ultimately moved to Middlesbrough in October 2000.
It was a missed opportunity that Bernstein has continued to reflect upon.
"One certainly was Ugo Ehiogu, a big central defender who Joe Royle spent a lot of time trying to get me to sign. And he went to Middlesbrough in the end.
"But I knew he was a very strong, powerful central defender. I suspect had we got him, we may not have gone down that season when we had Joe Royle â after the back-to-back promotions and we got relegated, I think we may have stayed up if we'd had him.
"He was a very strong, very high quality player."
It is an intriguing counterfactual. City had enjoyed successive promotions under Royle before struggling on their return to the Premier League, eventually suffering relegation in 2000.
Bernstein believed the addition of a commanding defender such as Ehiogu could have made a decisive difference.
The former chairman is careful not to suggest that one signing would automatically have transformed everything, but his recollection leaves little doubt that he regarded the defender as a major missed opportunity.
There were other players City wanted but could not secure, although Bernstein believes the club generally managed to land most of its preferred targets.
Talent alone was never enough
Looking back at the recruitment process, Bernstein also identifies a recurring problem that extended beyond transfer negotiations.
The club encountered players with obvious ability who never fulfilled their potential, something he believes remains one of football's more frustrating realities.
Asked whether there were players who could have achieved more, he was unwilling to identify individuals.
"Definitely, yes. But I'm not going to name them.
"It's the same thing, isn't it? It's this matching of talent with commitment. You know, and talent is not enough. You know, it needs that commitment, that discipline, that lifestyle commitment to giving up certain things that young people want to do and discipline yourself."
He points to Cristiano Ronaldo and Novak Djokovic as examples of elite sportspeople whose careers have been underpinned by extraordinary dedication to maintaining their physical condition.
Bernstein believes the difference between having the ability to succeed and actually reaching the top is often found away from the pitch.
"Of course there were players who had the talent but didn't have the rest of those things to go with it, which is a great shame. And I wonder how they must feel about their lives afterwards when they thought maybe they could have really done it, or they had a chance, they had an opportunity and they didn't take it."
For a chairman who witnessed Manchester City rebuilding from the bottom of the Football League, those lessons were part of a much bigger process.
Some signings became heroes, others provided glamour or professionalism, while a few never arrived at all. Bernstein's recollections offer a reminder that the transformation of a football club is rarely the product of one extraordinary transfer window.
Sometimes it is the last-minute signing who becomes a legend. Sometimes it is the player who got away who remains in the chairman's thoughts.
David Bernstein's book "We were really there: The Rebirth of Manchester City" is from Pitch Publishing - which is available here.

