Work on Cine-UK's eight-screen multiplex with four restaurant bar areas is set to start in May and it is anticipated the cinema will be open by early 2005.
"This is really good news for people throughout the borough," said Cllr John Griffiths, Leader of St Edmundsbury Borough Council.
"Many people have contacted me to say how much they are looking forward to having the opportunity to enjoy such a facility and I know this decision will be warmly welcomed.
"Those cinema-goers who drove to Ipswich or Cambridge will soon be able to come to Bury St Edmunds instead, which is excellent news for the prosperity of the borough."
Cllr Andrew Varley, portfolio holder for arts and culture, said: "I am absolutely delighted at the decision on the multiplex cinema. Virtually everyone in the borough has waited for this for a long time and at last we can look forward to it being built. I look forward to being one of the first customers."
A revised version of the scheme was given planning consent by St Edmundsbury Borough Council's development control committee, although 28 conditions were attached. The initial plan had caused a stir among both Bury Free Press readers and councillors on its appearance alone.
Many councillors still held reservations about the scheme and while Cllr Helen Levack suggested a small delay while the scheme was redesigned, not a single councillor voted against the scheme.
Susan Tamlyn, vice-president of the Suffolk Preservation Society, said the group had no objection to the application in principle – their objection was the 'cheap design'.
But Cllr Geoffrey Rushbrook said it looked exactly what it was – an entertainment area – while Cllr Mike Ames said schoolchildren said the design looked 'brilliant'.
"We have deliberated for over four or five years and we won't be thanked by the people who we are supposed to represent if we dilly dally anymore over this application," said Cllr Ames. "It will be a marvellous Christmas present for everyone in the borough and everyone in the region."
Chris Frost, from Halpern, representing Cine-UK, said: "We do feel that the building itself is in context with its surroundings."
Cllr Paul Farmer suggested changes to operating hours which allow the restaurants to stay open until midnight and the cinema until 2am.
But principal planning officer Peter Fuller said it was the same as granted to the previous Simons Estates scheme in November 1999, and Mr Frost said cinema-goers would cause little disturbance.
After the meeting, Stephen Wiener, chief executive of Cine-UK, said: "I feel very good about this. I'm just pleased that we are going to be given the opportunity to provide first-class entertainment to the area."