Between them, the top-seeded Swiss and number three Serb dropped just eight games. The pair who contested the US Open final less than five months ago spent a combined time of less than three hours on court.
Federer came down hard on Fabrice Santoro to see the flashy French danger man safely out with a no-nonsense 6-1, 6-2, 6-0 win. Djokovic hammered Italian Simone Bolelli 6-1, 6-2, 6-2.
"It's always good to start a Grand Slam with two-straight set wins," the Serb said. "I didn't want to underestimate anybody, even my opponent today.
"Obviously he was a little bit nervous, and he didn't get a lot of balls back. I just needed really to stay in the match and stay focused, just, you know, be myself, be aggressive, which I did."
Federer's efficient second-round thrashing of Santoro was the second-straight match at Melbourne Park in which the Swiss top seed had lost just three games.
Santoro, 35, is known for producing devilish tennis with his double-fisted attack combined with a mastery of spin and angles.
"I just really got off to a good start," said Federer, who is chasing a third-straight title at Melbourne Park. "After that, it was tough for him."
"I really didn't give him much. I think I really played him in a very smart way," said the Swiss, who had 53 winners and 14 unforced errors.
Federer came into the year's first major cold after being unable to compete last week in the Kooyong tune-up because of a stomach virus.
Federer now stands 9-2 against the Frenchman after losing two of their first three matches from 1999 to 2002.
He will play Saturday in the third round against Janko Tipsarevic after the Serb defeated Spaniard Fernando Verdasco 7-5, 7-6 (7-3), 7-6 (7-3).
Spanish fifth seed David Ferrer earned another fast win, beating Argentine Juan Del Potro Argentina, 6-3, 6-4, 6-0. Czech 13th seed Tomas Berdych stopped Spain's Oscar Hernandez 6-2, 6-1, 6-3 while former number one Juan Carlos Ferrero ended the dream of Australian wild card Alun Jones 6-4, 6-4, 6-2.
Aussie Lleyton Hewitt required more than three hours to beat number 217 Denis Istomin of Uzbekistan 7-6 (7-5), 6-3, 5-7, 6-1. Hewitt was forced to a fourth set after being broken while serving for victory in the third.
Women's seeds moved easily ahead with number two Russian Svetlana Kuznetsova leading the way past Tsvetana Pironkova of Bulgaria 7-6 (7-0), 6-2.
Venus Williams, the number eight, put out Frenchwoman Camille Pin 7-5, 6-4, but the win was far from pretty with 14 breaks of serve in the contest.
"I feel like I know how to play tennis, and whether or not I have my best match or a match that's not so good for me is not something that worries me for the next round," Williams said. "Either way, it's just important for me to get to the next round. I feel like I can always play better, even if I play well."
Russian sixth seed Anna Chakvetadze put out countrywoman Alisa Kleybanova 6-3, 6-4 while Daniela Hantuchova, the number nine, stopped French teenager Alize Cornet 6-2, 7-5.