Esimest korda ilmus leht Virumaa Teataja nime all aastatel 1925-1940, seejärel kandis see Punase Virumaa nime. Teistkordselt seisis päises Virumaa Teataja aastatel 1941-1944. Seejärel oli lehe nimeks Viru Sõna, Punane Täht ja taas Viru Sõna. Uue numeratsiooni järgi ilmus Virumaa Teataja number 18. septembril 1993. Sellest lugedes olemegi jõudnud 5000. numbrini.