Costa, the Brazil-born striker who is being courted by Spain, netted in each half of the 3-0 success, which was kick-started by Raul Garcia's 20th-minute opener.
While Diego Simeone's side now have a maximum of nine points, the hosts are struggling with just one from their first three games.
Atletico started aggressively with Juanfran striking from 25 yards and drawing an early save from Heinz Lindner.
The goalkeeper was unable to stop his side going behind after just eight minutes when Koke's clever pass released Luis Felipe and caught the home defence cold.
Felipe played the ball across goal for the advancing Garcia, who completed a straightforward finish.
Vienna's task got even harder just before the quarter-hour mark when leading striker Marko Stankovic pulled up with a recurrence of his recent calf trouble and was forced out of the game.
Roman Kienast replaced him in attack but Atletico were doing most of the pressing.
The game seemed to be Atletico's for the taking and Costa grabbed the initiative in the 20th minute.
He picked the ball up close to halfway, raced towards the final third and got clear of his man before finishing calmly as Lindner came to meet him.
The striker was off target at his next attempt, 10 minutes from the interval, after a delicate build-up between Felipe and Koke gave him room to shoot.
Hosiner almost halved the deficit with Vienna's first chance, clattering the woodwork with a back-post volley, but the visitors went in 2-0 up.
Costa made extended that eight minutes into after the restart, substitute Emiliano Insua breaking down the left before teeing up his team-mate's second of the night. There was no time for a hat-trick as Costa made way on the hour mark.
Koke nearly added to the tally direct from a corner when his curled effort deceived Lindner and hit the post.
Atletico might have increased their lead with better finishing in the closing stages but they appeared content to close out an impressive victory.