In a statement on their website, the Welsh club said: "The Board of Directors at Cardiff City have relieved Malky Mackay of his duties. A new first team manager will be appointed in due course."
Mackay, 41, who had been Cardiff manager since June 2011, ended their 51-year absence from the top flight in May when they gained automatic promotion to the Premier League after winning the Championship (second division).
He was widely-respected for the job he did and hugely popular with fans who have protested in recent weeks against Tan, the equally unpopular Malaysian owner of the club who inititally angered supporters by changing their kit from blue shirts to red before the start of last season.
In a statement issued after the sacking Tan said: "Far too much dirty linen has been exposed to the public gaze, but I stress, not by me.
"Indeed I have deliberately not responded to this, hoping the club can be judged by its football rather than personalised arguments about who said what to whom.
"I have however regretfully concluded that it is no longer fair to the club, its players, its fans and public, more generally, for this uncomfortable state of affairs to continue."
Cardiff, relegated from the top flight in 1962, spent decades floundering in the third and fourth tiers of the league before beginning the slow climb back 12 years ago.
Under predecessor David Jones and then Mackay, Cardiff established themselves in the second tier and began to make solid progress with Forbes billionaire Tan adding his considerable financial muscle to the club when he took control in 2010.
With Tan and Mackay at the helm, Cardiff reached the League Cup final in 2012 when they lost to Liverpool on penalties and also reached the promotion playoff semi-finals, losing to West Ham United.
However, their long absence from the top flight ended last season when they were promoted as Championship winners, and their first home league match ended in a 3-2 win over title hopefuls Manchester City.
But the deteriorating relationship between Mackay and Tan was made public soon after the start of the season when Tan appeared to question spending more than 25.0 million pounds strengthening the squad to boost their chances of avoiding a swift return to the second division.
There was a public spat over the budget and the transfer fees spent, then Tan sacked Mackay's long-term right-hand man Ian Moody, the club's head of recruitment, replacing him with a 23-year-old friend of his son who had no experience in football.
In October, Tan said he had "every faith in Malky and his team to lead us through the challenges of the Premier League."
But in words that proved to be rather hollow, he added: "I have supported him in the past and will do so in the future for many years to come."
Their relationship did not improve in the weeks that followed and virtually reached breaking point last weekend when Mackay refused to resign as manager after being handed an ultimatum to either "resign or be sacked".
Mackay's last game in charge was Thursday's 3-0 home defeat to Southampton which left the club 16th in the 20-team division, one point and two places above the relegation zone.
He has become the sixth Premier League manager to lose his job this season following Paolo Di Canio (Sunderland), Ian Holloway (Crystal Palace), Martin Jol (Fulham), Steve Clarke (West Bromwich Albion) and Andre Villas-Boas (Tottenham Hotspur).
Now managerless Cardiff play Sunderland at home on Saturday with Sven-Goran Eriksson and Ole Gunnar Solskjaer among those linked to succeeding the Scot who is not expected to remain out of work for long.
Image: Cardiff City manager Malky Mackay
Photograph: Clive Brunskill/Getty Images
EPL: Suarez dreams as race goes into festive overdrive
BEST Sports Photos of the Year: Part II
Murray's Wimbledon win, Sachin's goodbye.. Top sporting moments of 2013
Highlights of 2013 Indian football: Bagging rights of hosting U-17 WC
EPL PHOTOS: Walcott lifts Arsenal, City sink Liverpool