Jabarkan Karier dari Gong Hyo-jin

Setelah kembali ke Korea, Hyo-jin mulai bekerja sebagai model. Dia muncul dalam iklan yang cukup populer yaitu "Happy to Death" untuk telekomunikasi 700-5425. Setelah satu setengah tahun menjadi model, ia melakukan debut aktingnya sebagai peran pendukung di Memento Mori. Disutradarai oleh Kim Tae-yong dan Min Kyu-dong, film horor ini menemukan kembali genre dengan pendekatan segar pada seksualitas wanita remaja dan kekuatan destruktifnya serta menyatukan sapphisme dan supranatural di sekolah menengah khusus perempuan. Meskipun tidak menjadi film box office pada tahun 1999, film ini sering dikutip oleh para pembuat film muda Korea dan penggemar bioskop sebagai film yang klasik dan modern. Pada awalnya Hyo-jin tidak begitu serius menekuni akting dan selalu tidak sabar menunggu syuting segera berakhir, tetapi keberhasilan secara kritis Memento Mori mendorongnya untuk terus berakting dan ia melanjutkannya dengan berperan dalam sitkom My Funky Family pada tahun 2000.

Pada tahun 2001, ia berperan dalam seri televisi berjumlah 50 episode dengan judul Wonderful Days sebagai kondektur bus yang memiliki perasaan tak terbalas kepada karakter Ryoo Seung-bum (karena peran tersebut Hyo-jin dan Seung-bum memenangkan Best New Actress dan Best New Actor dalam kategori televisi di Baeksang Arts Awards). Setelah muncul sebagai peran kecil dalam film komedi Guns & Talks yang disutradarai oleh Jang Jin dan film seni bela diri remaja Volcano High, aktris muda ini membuat terobosannya pada tahun 2002 dengan menjadi pemeran utama dalam Emergency Act 19 dan A Bizarre Love Triangle.

Penampilan Hyo-jin di Ruler of Your Own World menarik perhatian industri. Seri televisi ini dipuji karena penulisannya yang realistis dan akting yang kuat serta membuatnya mendapat status "drama mania" (atau cult hit) di Korea Pada tahun yang sama, ia kembali berakting dengan Ryoo Seung-bum dalam Conduct Zero dan mendapatkan pujian untuk perannya sebagai "bos" yang berbicara dengan keras di sekolah menengah khusus perempuan. Film komedi bertema retro tahun 1980-an ini diterima dengan baik oleh penonton dan kritikus.

Seri televisi tahun 2003 berjudul Snowman memasangkan Hyo-jin dengan Cho Jae-hyun dan Kim Rae-won dengan plot kontroversial tentang seorang gadis yang jatuh cinta dengan kakak iparnya Dia kemudian muncul di Sang Doo! Let's Go to School yang disutradarai oleh Lee Hyung-min yang sebelumnya pernah bekerja dengannya dalam episode Drama City. Hyo-jin berperan sebagai guru sekolah menengah atas yang bertemu dengan kekasih masa kecilnya yang sekarang menjadi gigolo dan ayah tunggal bersama putrinya yang sakit. Drama ini merupakan debut akting dari penyanyi pop Rain dan berhasil meraih peringkat yang bagus serta Hyo-jin memenangkan beberapa penghargaan di KBS Drama Awards.

Pada tahun 2004 hingga 2005, Hyo-jin mengalami kemerosotan karier. Dia tidak puas dengan naskah yang dia dapatkan dan merasa dia sedang mengalami typecast dalam peran ingenue. Berperan sebagai guru sekolah menengah atas lainnya di Hello My Teacher dan sebagai seorang ilmuwan di Heaven's Soldiers, Hyo-jin sangat ingin memerankan peran yang lebih sederhana sebagai "wanita sejati" tetapi ia tidak mau melakukan ketelanjangan dalam film.