The influential Zao (Greek for "alive") began in 1996 in Parkersburg, WV (later relocating to Greensburg, PA), when Smith gathered some friends together with the intention of starting a ministry-oriented, faith-based hardcore band similar to so-called "spirit-filled" bands like Unashamed and secular acts Unbroken and Earth Crisis. He bought his first drum kit the weekend he formed the band. Their first release was a split with the band Outcast on a small Ohio label, followed by the All Else Failed full-length album. This gained the attention of Seattle's Tooth & Nail Records, which signed the band to a lengthy contract and released The Splinter Shards the Birth of Separation in 1997. Zao became the flagship act for the label's hardcore-oriented Solid State imprint.

After touring for the album, Smith found himself without a lineup as every other member exited following 1997's Cornerstone Fest. Determined to press forward, he recruited guitarists Brett Detar and Russ Cogdell and vocalist Daniel Weyandt, and without a bassist redefined the Zao sound and produced the awe-inspiring Where Blood and Fire Bring Rest, a mournful, poetic, and incisive metallic testament to perseverance and overcoming all odds. The album signaled a shift in focus from an outright preaching of Christianity to more personalized wordplay. It also saw the band musically moving far away from their initial influences and defining themselves as a formidable entity all their own. Zao toured relentlessly behind the album's release, and in 1998 produced a split with one of their touring mates, Sacramento, CA's Training for Utopia, dubbed simply Training for Utopia/Zao.

Detar left the group shortly after the EP's release to focus on his then side project the Juliana Theory. He was replaced by former Creation Is Crucifixion guitarist Scott Mellinger. Rob Horner was the next man to join the group, filling the long-vacant bass position. This lineup crafted Liberate Te Ex Inferis, a slightly more experimental yet still heavy album, in 1999. The album incorporated Neurosis-like meditations, further lyrical storytelling (including the tale of a doomed, true-to-life porn star), and flashy photography. Horner left briefly and Weyandt took over bass duties in addition to singing. Cory Darst replaced Weyandt for one tour as Horner returned. Cogdell left next as Weyandt returned, with Zao making Self-Titled in late 2000 as a four-piece and releasing it that same year. The album served as an all-new Zao mission statement, building on the band's past strengths while dipping into moody atmospherics reminiscent of Portishead, Massive Attack, or perhaps even the often-cited Radiohead.

Shortly after the album's release, Darst replaced Weyandt full-time as an official member of the band. In 2001, Zao recorded three songs at a Seattle studio and toured with renewed vigor. In early 2002, both Horner and Darst exited the band, with Weyandt and Cogdell coming back aboard as Zao resigned to Solid State for two more albums. Parade of Chaos appeared in July, a month before that lineup of Zao broke up. This was far from the end, however, and the band reunited for two Cornerstone performances in 2003 and was permanently back together by the year's end. (Society's Finest vocalist Joshua Ashworth briefly replaced Weyandt.) A series of demos was cut that same year for a fledgling label that never quite got off the ground, so the band was instead snatched up by Ferret. Meanwhile, the best-of album Legendary surfaced the following year via Solid State.

By now, Zao included Weyandt, Mellinger, and Cogdell alongside new recruits Shawn Koschik (bass) and Stephen Peck (drums). Together, they recorded their Ferret debut, the conceptual The Funeral of God, which was released in the summer of 2004; it earned the guys praise from the metal scene and their first airplay on MTV. Lots of touring commenced over the next two years, playing well-received sets with bands like the Dillinger Escape Plan, the Juliana Theory, and Every Time I Die. Peck made his leave in mid-2005 and was replaced on drums by Jeff Gretz in time for U.S. and U.K. dates with Bleeding Through and their stint on the summer's Warped Tour. During Warped, however, Cogdell suffered a knee injury, which ultimately caused his departure. That fall Zao continued on as a four-piece comprised of Mellinger, Weyandt, Gretz, and bassist Marty Lunn. The Steve Albini-produced The Fear Is What Keeps Us Here was next issued in the summer of 2006. Early the next year, a healed-up Cogdell rejoined Zao's ranks as Gretz left to join From Autumn to Ashes.