Ida-Harju nädalalehe Sõnumitooja esimene number ilmus 26. oktoobril 1994. aastal.
Sõnumitooja asutasid Anija, Kuusalu, Loksa ja Raasiku vald ning Kehra ja Loksa linn. ASi Sõnumitooja asutamiskoosolek toimus 9. septembril 1994. Asutamiskoosolekul esindasid omavalitsusi Anija vallavanem Tõnis Väli, Kuusalu vallavanem Urmas Kirtsi, Loksa vallavanem Andres Allmägi, Raasiku vallavanem Toivo Veenre, Kehra linnapea Jüri Lillsoo ja Loksa linnapea Andres Kaskla. Ettevõtte juhatusse valiti Urmas Kirtsi, Toivo Veenre ja Andres Kaskla. Juhatuse esimeheks sai Urmas Kirtsi.
Ajalehe Sõnumitooja peatoimetajaks kinnitati Ülle Tamm Loksalt. Ta töötas siis ajalehes Harjumaa, oli Kuusalu piirkonna korrespondent. Ta on lõpetanud Tartu Riikliku Ülikooli 1986. aastal ajakirjaniku diplomiga. Toimetuses töötasid esialgu veel autojuht ja fotograaf Enno Tikerpalu Viinistult ning ärijuht Peep Abel ja küljendaja Viive Abel Kiiust.

Sõnumitooja on alates esimesest numbrist ilmunud kord nädalas kolmapäeviti. Kuni 1994. aasta lõpuni oli leht neljaleheküljeline, alates jaanuarist 1995 kaheksa leheküljega. Omavalitsused hakkasid lehe väljaandmist rahaliselt toetama.
21. augustil 1996. aastal otsustas osanike üldkoosolek muuta aktsiaselts osaühinguks. Juhatuse esimehed on olnud peale Urmas Kirtsi veel Loksa linnavolikogu esimees Rein Heina ja Raasiku vallavanem Andre Sepp. Kui aastal 2000 muudeti seadust, omavalitsusjuhid ei tohtinud enam olla äriühingute juhatuses, muudeti OÜ Sõnumitooja põhikirja. Üheliikmelise juhatuse liikmeks nimetati 2000. aasta suvel Sõnumitooja peatoimetaja Ülle Tamm. Sõnumitooja juhatuse liikmed ei ole saanud töötasu ega hüvitust. Toimetus on olnud Kiiu mõisas Kuusalu vallamajas. Kiiu mõisa remondi ajaks sai toimetus ruumid Kuusalu tehase administratiivhoones.
Sõnumitooja algusaastatel töötasid korrespondentidena Merle Korjus Raasikult, Marianne Leis Anija vallast, Sirkka Kaasik Kuusalu vallast. 12. veebruaril 1996 asus vanemtoimetajana tööle Külli Koppelmaa, kes oli selle ajani maakonnalehe Harjumaa ajakirjanik. Tema lapsepuhkuse ajal on Sõnumitooja ajakirjanikena töötanud Kristjan Arunurm, Tene Hook, Gertrud Vinter (Kaljuvee), Lauri Leet, Katrina Helstein, Kadri Põlendik, Eve Kruuse, Merike Metstak. Aasta 2013 juulis tuli ajakirjanikuna tööle Ere Uibo, kel on Tartu Ülikooli ajakirjanduseriala diplom. Ta töötas toimetuses augustini 2018. Sügisel 2018 oli Sõnumitooja ajakirjanik Anne Martin.
Leht ilmus aastaid mustvalgena, veebruarist 2014 osaliselt ja 2021. aasta juuli lõpust on ilmunud üleni värvilisena. Veebruarist 2014 kuni 2023. aasta suveni levitati tasuta Sõnumitoojat kord kuus piirkonna kõigisse postkastidesse. Sügisest 2023 jagame tasuta lehte kord kuus kohalikes kauplustes. Aastatel 2015-2019 oli Sõnumitoojal pidevalt või osaliselt 12 lehekülge.
Praeguseks on OÜ-le Sõnumitooja jäänud kolm omanikku: Anija, Kuusalu ja Raasiku vald. Koos 2002. aasta valimistega liitusid Anija vald ja Kehra linn. Aasta 2005 kevadel loobus osalemisest Loksa linn. 2005 sügisel ühinesid Kuusalu vald ja Loksa vald. Aastal 2017 liitusid koos kohalike valimistega Anija vald ja Aegviidu vald, lehepiirkonda lisandus Aegviidu alev.
Ajalehe nimeks valiti Sõnumitooja 1994. aastal seetõttu, et Kehra tselluloositehases anti välja infolehte Sõnumitooja, ka Kuusalu kolhoosi häälekandja nimi oli Sõnumitooja. Sama nime kandis Kuusalu vallas kord kuus ilmunud infoleht, mille tegemine lõpetati, kui asutati maakonnaleht Sõnumitooja.