After setting the third fastest lap in qualifying, behind polesitter Lewis Hamilton and Red Bull team-mate Mark Webber, Vettel was ordered to stop his car on his in-lap at the Yas Marina Circuit.
Following a lengthy stewards' investigation into the matter, Vettel's demotion was not declared until four hours and 40 minutes after the qualifying session had concluded.
The 25-year-old German now faces a battle just to get into the points and it is almost certain championship rival Fernando Alonso will close the 13-point gap between them.
The statement from the FIA read: "The stewards received a report from the race director (Charlie Whiting) that car one (Vettel) failed to return to the pits under its own power as required under article 6.6.2 of the FIA Formula One technical regulations.
"The stewards heard from the driver and team representatives and studied telemetry evidence that showed the reason why the car was stopped.
"The stewards accepted the explanation and considered the incident as being a case of force majeure.
"However, a report was received from the technical delegate that showed during post-qualifying scrutineering an insufficient quantity of fuel for sampling purposes.
"The stewards determine this is a breach of article 6.6.2 of the FIA Formula One technical regulations and the competitor is accordingly excluded from the results of the qualifying session.
"The competitor is, however, allowed to start the race from the back of the grid."
The incident is virtually identical to the one involving Hamilton following qualifying for the Spanish Grand Prix in Barcelona in May.
Hamilton set the fastest lap that day and what should have been McLaren's 150th pole, but like Vettel, was ordered to stop on track.
This is a breach of the rules as the car is required to return to the pits for scrutineering and then have a litre of fuel remaining for a sample to be taken.
Team boss Martin Whitmarsh claimed 1.3 litres of fuel were extracted, however, the additional 0.3 litres - over and above the required one litre - was deemed by the stewards not enough to see Hamilton return to the pits bearing in mind he stopped at around halfway.
McLaren attempted to argue their own force majeure case that day, but the stewards dismissed their argument and Hamilton was dumped to the back of the grid, eventually going on to finish eighth.
In this instance, Red Bull were able to show there was an issue with the car, resulting in Vettel pulling over to one side.
However, like Hamilton, technical delegate Jo Bauer discovered the car was short on fuel, resulting in the same penalty as the one handed out to the Briton.
The incident would appear to throw the title race wide open again bearing in mind Vettel has crushed his rivals in winning the last four races.
Watch: Vettel demoted to back of grid... More Videos
Returning from the summer break trailing Alonso by 44 points, Red Bull and Vettel suddenly found their form again from the Singapore Grand Prix onwards and seemed set to cruise to their third consecutive championships.
But providing Alonso can finish the race and bring his car home in a respectable position, there is now every chance his fight with Vettel to become the ninth driver in F1 history to win a third title will go down to the wire.
The Vettel penalty means everybody behind the German will move up a place on the grid, with Alonso notably now starting sixth.
Ahead of him on the grid, aside from Hamilton and Webber on the front row, will be Williams' Pastor Maldonado, Kimi Raikkonen in his Lotus and the second McLaren of Jenson Button.