Robert Lewandowskis straff gav de tyska mästarna huvudrollen innan Thomas Muller kom hem på sin 27-årsdag.
Joshua Kimmich knivhögg in och lade snabbt till en rubrik som Bayern boss Carlo Ancelotti blev den första mannen att hantera sju klubbar i tävlingen.
Juan Bernat sköt in från 10 yards för 5-0. Atletico Madrid vann 1-0 på PSV i Grupp D:s andra spel.
Kimmich, 21, har nu gjort sitt första mål för Tyskland, första Bayern München ligan mål och första Champions League mål i en 10-dagars period.
Efter att ha slagit den ryska sidan, Ancelotti, som har vunnit turneringen tre gånger som manager, sade: "Kan vi vinna Champions League? För säker på att vårt lag kommer att vara konkurrenskraftig denna säsong och för tillfället allt är bra, men det första målet är att vinna gruppen, och sedan kommer vi att se dragningen. "
Den engelske domaren Martin Atkinson uteslöt "ett bra mål", enligt PSV-chefen Phillip Cocu, efter att Luuk de Jongs femte minuters insats inte tilläts i Eindhoven.
Saul Niguez scissor kick från 18 yards visade sig avgörande för Attetico, som hade målvakt Jan Oblak att tacka för att spara Andres Guardado straff på slag av halvtid.
I Grupp B producerade Anderson Talisca en fantastisk 93:e minuts frikick för att tjäna Besiktas en 1-1 dragning mot sin föräldraklubb Benfica.
"Det är en dragning som känns som en seger", säger Besiktas mittfälter Ricardo Quaresma.
Talisca strejk i Lissabon lämnar båda sidor driver Napoli, som kom bakifrån som sommaren underteckna Arkadiusz Milik slog två gånger på nio minuter för att se över Dynamo Kievs ledning före halvtid i Ukraina.
Den italienska sidan netted med sina enda två skott på mål mot Kiev målvakt Oleksandr Shovkovski, som blev den näst äldsta spelaren i Champions League historia på 41 år och 255 dagar. Ex-Lazio spelaren Marco Ballota är fortfarande den äldsta på 43 år och 252 dagar.
Bulgariska sidan Ludogorets - i Champions League grupp scenen för andra gången - inför 14 skott vid Basel men lämnade Schweiz med en 1-1 dragning, matchar det andra resultatet i gruppen mellan Paris St-Germain och Arsenal i Paris.
Barcelona producerade stand-out resultat av natten som Lionel Messi slog en hatt-trick i en 7-0 seger över Celtic, medan den andra fixturen i Grupp C mellan Manchester City och Borussia Monchengladbach har omplanerats till onsdag på grund av dåligt väder.
Matchändar, FC Bayern München 5, FC Rostov 0.
Andra halvlek, FC Bayern München 5, FC Rostov 0.
Försök missade. David Alaba (FC Bayern München) vänster fotade skott från utsidan lådan är nära, men missar till höger från en direkt frispark.
Renato Sanches (FC Bayern München) vinner en frispark i anfallshalvan.
Foul av Aleksandru Gatcan (FC Rostov).
Mål!  FC Bayern München 5, FC Rostov 0. Juan Bernat (FC Bayern München) vänster fotade skott från mitten av lådan till mitten av målet. Hjälpt av Franck Ribery.
Franck Ribéry (FC Bayern München) vinner en frispark på vänsterflygeln.
Foul av Aleksandru Gatcan (FC Rostov).
Försök blockerat. Franck Ribéry (FC Bayern München) höger fotade skott utanför lådan är blockerad. Hjälpt av Robert Lewandowski.
Joshua Kimmich (FC Bayern München) vinner en frispark i defensiva halvan.
Foul av Denis Terentjev (FC Rostov).
Hörnet, FC Bayern München. Sammankallad av Vladimir Granat.
Försöket räddades. Aleksandr Erokhin (FC Rostov) huvud från mitten av rutan sparas i det övre högra hörnet. Hjälpt av Timofei Kalachev.
Foul av Arturo Vidal (FC Bayern München).
Moussa Doumbia (FC Rostov) vinner en frispark i anfallshalvan.
Offside, FC Bayern München. Arturo Vidal försöker en genom boll, men Franck Ribery fångas offside.
Försök missade. Timofei Kalachev (FC Rostov) höger fotade skott från höger sida av lådan är för hög. Hjälpt av Aleksandr Erokhin.
Hörnet, FC Rostov. Förföljd av Javi Martínez.
Javi Martínez (FC Bayern München) vinner en frispark i defensiva halvan.
Foul av Moussa Doumbia (FC Rostov).
Försök blockerat. David Alaba (FC Bayern München) vänster fotade skott utanför lådan är blockerad.
Franck Ribéry (FC Bayern München) vinner en frispark i anfallshalvan.
Foul av Aleksandru Gatcan (FC Rostov).
David Alaba (FC Bayern München) vinner en frispark på vänsterflygeln.
Foul av Aleksandr Erokhin (FC Rostov).
Foul av Joshua Kimmich (FC Bayern München).
Moussa Doumbia (FC Rostov) vinner en frispark i defensiva halvan.
Ersättning, FC Bayern München. Renato Sanches ersätter Thiago Alcántara.
Foul av Arturo Vidal (FC Bayern München).
Timofei Kalachev (FC Rostov) vinner en frispark i defensiva halvan.
Foul av Javi Martínez (FC Bayern München).
Aleksandr Erokhin (FC Rostov) vinner en frispark i anfallshalvan.
Försening över. De är redo att fortsätta.
Ersättning, FC Bayern München. Franck Ribéry ersätter Douglas Costa.
Ersättning, FC Rostov. Andrei Prepelita ersätter Sardar Azmoun.
Försening i match Soslan Dzhanaev (FC Rostov) på grund av en skada.
Försöket räddades. Arturo Vidal (FC Bayern München) vänster fotade skott från utsidan rutan sparas i det övre högra hörnet. Hjälpt av Thiago Alcántara.
Mål!  FC Bayern München 4, FC Rostov 0. Joshua Kimmich (FC Bayern München) huvudet från mitten av rutan till nedre högra hörnet. Hjälpt av Juan Bernat efter ett hörn.
Hörnet, FC Bayern München. Sammankallad av Denis Terentjev.
Försök missade. Robert Lewandowski (FC Bayern München) höger fotade skott från mitten av lådan är för hög. Hjälpt av Douglas Costa.
Bayern München började sitt bud på en sjätte EM-titel genom att hamra Champions League debutanter Rostov 5-0.