Anderson, the 19th seed, came back from two sets down to win a five-set thriller 2-6, 6-7 (4/7), 6-4, 6-4, 6-4.
Anderson will play unheralded Australian Dominic Thiem in the second round.
Thiem accounted for Portugal's Joao Sousa 5-7, 6-4, 6-3, 7-6 (7/3) in their first round encounter.
Results from the Australian Open on Monday:
Men's singles
First round
Stanislas Wawrinka (SUI x8) bt Andrey Golubev (KAZ) 6-4, 4-1 ret
Ivan Dodig (CRO x32) bt Ivo Karlovic (CRO) 7-6 (10/8), 6-3, 7-6 (7/4)
Mikhail Youzhny (RUS x14) bt Jan-Lennard Struff (GER) 6-1, 6-4, 6-2
Sam Querrey (USA) bt Santiago Giraldo (COL) 6-3, 6-2, 3-6, 7-6 (7/3)
Damir Dzumhur (BIH) bt Jan Hajek (CZE) 6-4, 6-2, 6-1
Adrian Mannarino (FRA) bt Steve Johnson (USA) 3-6, 6-3, 6-0, 5-7, 6-4
Richard Gasquet (FRA x9) bt David Guez (FRA) 7-5, 6-4, 6-1
Tomas Berdych (CZE x7) bt Aleksandr Nedovyesov (KAZ) 6-3, 6-4, 6-3
Dominic Thiem (AUT) bt Joao Sousa (POR) 5-7, 6-4, 6-3, 7-6 (7/3)
David Ferrer (ESP x3) bt Alejandro Gonzalez (COL) 6-3, 6-4, 6-4
Jarkko Nieminen (FIN) bt Dudi Sela (ISR) 3-6, 7-6 (7/3), 6-7 (3/7), 6-3, 6-3
Florian Mayer (GER) bt Denis Kudla (USA) 6-4, 6-2, 6-4
Alejandro Falla (COL) bt Mikhail Kukushkin (KAZ) 6-7 (2/7), 6-2, 6-2, 6-3
Guillermo Garcia-Lopez (ESP) bt Tommy Haas (GER x12) 7-5, 5-2 ret
Julien Benneteau (FRA) bt Pablo Carreno Busta (ESP) 6-3, 3-6, 4-6, 6-1, 6-2
Kevin Anderson (RSA x19) bt Jiri Vesely (CZE) 2-6, 6-7 (4/7), 6-4, 6-4, 6-4
Matthew Ebden (AUS) bt Nicolas Mahut (FRA) 6-3, 7-5, 4-6, 0-6, 6-3
Jeremy Chardy (FRA x29) bt Jesse Huta Galung (NED) 6-2, 6-4, 6-4
Fabio Fognini (ITA x15) bt Alex Bogomolov Jr. (RUS) 6-3, 6-2 ret
Ernests Gulbis (LAT x23) bt Juan Monaco (ARG) 1-6, 6-4, 7-6 (7/4), 6-2
Leonardo Mayer (ARG) bt Albert Montanes (ESP) 6-1, 6-3, 6-1
Kenny De Schepper (FRA) bt Wu Di (CHN) 7-5, 7-5, 7-6 (7/2)
Jerzy Janowicz (POL x20) bt Jordan Thompson (AUS) 1-6, 4-6, 6-4, 6-2, 6-1
Edouard Roger-Vasselin (FRA) bt Carlos Berlocq (ARG) 6-4, 7-6 (7/5), 6-7 (9/11), 6-2
Tommy Robredo (ESP x17) bt Lukas Rosol (CZE) 6-1, 6-7 (7/9), 3-6, 7-6 (7/5), 8-6
Pablo Andujar (ESP) bt Albert Ramos (ESP) 6-4, 6-2, 6-4
Vasek Pospisil (CAN x28) bt Samuel Groth (AUS) 6-4, 6-3, 6-4
Dmitry Tursunov (RUS x30) bt Michael Russell (USA) 6-2, 6-2, 6-3
Alexandr Dolgopolov (UKR) bt Ricardas Berankis (LTU) 7-5, 7-5, 6-2
Novak Djokovic (SRB x2) bt Lukas Lacko (SVK) 6-3, 7-6 (7/2), 6-1
Nikolay Davydenko (RUS) bt Lukasz Kubot (POL) 3-6, 6-3, 3-6, 6-3, 6-4
Denis Istomin (UZB) bt Marcos Baghdatis (CYP) 6-4, 7-5, 6-4
Women's singles
First round
Kirsten Flipkens (BEL x18) bt Laura Robson (GBR) 6-3, 6-0
Angelique Kerber (GER x9) bt Jarmila Gajdosova (AUS) 6-3, 0-6, 6-2
Belinda Bencic (SUI) bt Kimiko Date-Krumm (JPN) 6-4, 4-6, 6-3
Alla Kudryavtseva (RUS) bt Caroline Garcia (FRA) 6-2, 7-6 (9/7)
Monica Puig (PUR) bt Anna Tatishvili (GEO) 6-2, 6-4
Irina Falconi (USA) bt Anabel Medina Garrigues (ESP) 6-3, 6-1
Karolina Pliskova (CZE) bt Pauline Parmentier (FRA) 6-0, 6-1
Daniela Hantuchova (SVK x31) bt Heather Watson (GBR) 7-5, 3-6, 6-3
Ekaterina Makarova (RUS x22) bt Venus Williams (USA) 2-6, 6-4, 6-4
Casey Dellacqua (AUS) bt Vera Zvonareva (RUS) 6-2, 6-2
Li Na (CHN x4) bt Ana Konjuh (CRO) 6-2, 6-0
Eugenie Bouchard (CAN x30) bt Hao Chen Tang (CHN) 7-5, 6-1
Ana Ivanovic (SRB x14) bt Kiki Bertens (NED) 6-4, 6-4
Annika Beck (GER) bt Petra Martic (CRO) 6-0, 6-0
Virginie Razzano (FRA) bt Alison Van Uytvanck (BEL) 7-6 (7/3), 7-6 (7/3)
Lucie Hradecka (CZE) bt Donna Vekic (CRO) 6-3, 6-1
Flavia Pennetta (ITA x28) bt Alexandra Cadantu (ROU) 6-0, 6-2
Vesna Dolonc (SRB) bt Lara Arruabarrena (ESP) 2-6, 6-2, 6-4
Lucie Safarova (CZE x26) bt Julia Glushko (ISR) 7-5, 3-6, 6-1
Zheng Jie (CHN) bt Roberta Vinci (ITA x12) 6-4, 6-3
Mona Barthel (GER) bt Zhang Shuai (CHN) 7-6 (7/4), 6-3
Monica Niculescu (ROU) bt Shahar Peer (ISR) 6-4, 6-1
Julia Goerges (GER) bt Sara Errani (ITA x7) 6-3, 6-2
Madison Keys (USA) bt Patricia Mayr-Achleitner (AUT) 6-2, 6-7 (8/10), 9-7
Samantha Stosur (AUS x17) bt Klara Zakopalova (CZE) 6-3, 6-4
Tsvetana Pironkova (BUL) bt Silvia Soler-Espinosa (ESP) 6-3, 6-2
Sabine Lisicki (GER x15) bt Mirjana Lucic-Baroni (CRO) 6-2, 6-1
Luksika Kumkhum (THA) bt Petra Kvitova (CZE x6) 6-2, 1-6, 6-4
Alison Riske (USA) bt Elena Vesnina (RUS x23) 6-2, 6-2
Yanina Wickmayer (BEL) bt Dinah Pfizenmaier (GER) 7-6 (7/5), 6-3
Lauren Davis (USA) bt Sachia Vickery (USA) 6-3, 6-3
Serena Williams (USA x1) bt Ashleigh Barty (AUS) 6-2, 6-1