Demo zwróciło uwagę innego członka dc Talk, TobyMaca, który pomógł Relient K podpisać kontrakt z wytwórnią Gotee Records. Dzięki nowej wytwórni w 2000 roku zespół wydał debiutancki EP – 2000 A.D.D. wraz z nowym perkusistą, Stephenem Crushmanem. Niedługo później ukazał się ich pierwszy album studyjny – Relient K. Styl muzyczny, jakim określił się wtedy zespół to rock chrześcijański. Wkrótce potem Crushman opuścił grupę na rzecz zespołu Narcissus (metal chrześcijański). Puste miejsce po perkusiście szybko zajęli jednak Bret Schoneman (Philmore), Jared Byers (Bleach) oraz Dave Douglas.
W jednym z wywiadów Matt Thiessen przyznał, że w początkowych latach działalności zespołu był on jedynym wokalistą. Wiedział jednak, że jego imiennik potrafi śpiewać równie dobrze, więc gorąco zachęcał Hoopesa do podjęcia drugiego wokalu.
The Anatomy of the Tongue in Cheek (2001 – 2002) W 2001 roku światło dzienne ujrzał drugi studyjny album zespołu – The Anatomy of the Tongue in Cheek. Krytycy przyznali, że Relient K „zwolnili tempo” i „przerzucili się” na lekkie, soft rockowe brzmienia.