Il club è stato fondato il 6 gennaio 1996 come squadra rappresentativa dell'omonima università.[1]
Nell'anno di fondazione partecipò al campionato di terza divisione distrettuale, vincendolo.[1] Nel 1998 vinse anche il campionato di seconda divisione.[1] Nel 1999, alla prima partecipazione nel torneo di prima divisione distrettuale, si guadagnò il rispetto delle squadre predominanti della città, lottando sino all'ultimo per il titolo e piazzandosi infine secondo.[1]
Nel 2001 il Cesar Vallejo vinse il titolo distrettuale, provinciale e dipartimentale. Raggiunse la finale di Copa Perú di quell'anno, venendo sconfitto dal Deportivo Bolito.[1]
Disputò un buon torneo anche l'anno dopo, ma fu il 2003 l'anno della consacrazione: la vittoria della Copa Perù regalò alla squadra di Trujillo la promozione nella Primera División, la massima serie nazionale.[2]
Militò per due anni consecutivi (2004 e 2005) al massimo livello, poi retrocesse.[1] Nel 2007 riconquistò la promozione alla massima serie.[1]
Nella stagione 2009 ottenne un sesto posto finale che qualificò la squadra alla Coppa Sudamericana 2010.[1]