Ega keegi ju ei tea täpselt, mil esimene kahejalgne siin neis paigus püsivalt kanda kinnitas ja omale esimese onnikese ehitas. Arheoloogid väidavad, et kunagi aastatuhandete eest jalutasid Tudulinna mail ringi armsad loomakesed mammutid, kelle võhkasid on väljakaevamistel leitud. Legendid räägivad hõimurahvastest vadjalastest ja isuritest, kes siinkandis aegu tagasi lühemat või pikemat aega paiksed olnud. Kuid konkreetset ajalugu saame arvestama hakata ikkagi kirjalike ajalooliste allikate alusel.
Varaseima teadaoleva kirjaliku ülestähenduse leidmiseks Tudulinna kohta peame rändama ajas tagasi 16. sajandi lõpukümnenditesse. Eesti alad kuulusid siis Rootsi kuningavõimu alla, seda juba alates 1561. aastast. Oli nn Rootsi aeg, mis rahvapärimustes on mõnikord leidnud mainimist kui „kuldne Rootsi aeg“. See on ajaloolaste hinnangul küll pigem eksitav kujund, sest tollesse ajajärku langesid mitmed sõjad, katku- ja näljahädad. Ehk on kujutluspilt õnnelikust rootsi ajast tekkinud pigem seetõttu, et Rootsi riigistas kõik varasemad rüütlimõisad ning nende ikkes olnud talupojad said vabatalupoegade staatuse. Nii kestis see kuni Põhjasõjani ja Eesti alade langemiseni Vene tsaaririigi koosseisu.
Tollest kaugest ajast säilinud kirjalikud materjalid ei pruugi olla täielikud ning on aegade keerises sattunud Rootsi, Eesti ja ka Läti arhiividesse. Põhiliselt tuleb otsida vakuraamatuid (kuhu pandi kirja talud ja nendele määratud koormised) ning üldiste revisjonide protokolle (neis tähendati üles külad, maksud jne). Sageli on tolleaegsete kirjutajate käekiri raskesti loetav ning vajab arusaamiseks spetsialisti abi. Mida kaugemasse aega tagasi liigume, seda katkendlikumad andmed alles on. Nii mõnigi dokument on sajandite keerises kaotsi läinud.
Praegustel andmetel on Tudulinna esimest korda kirjalikult märgitud just ühes niisuguses vakuraamatus. Ametliku nimega „Gert Höjeri Rakvere linnuselääni ja Toolse lääni vakuraamat 1583“ asub Rootsi Riigiarhiivis. Seal, leheküljel 24 on kirjas „Tutinlinna by“ ning järgmised ajaloolised andmed (tõlge: Ülle Tarkiainen):
Tudulinna küla 10 adramaad
Jahnus Kubjas ½ adramaad
- Vakuraha 2 taalrit
- Rukis 1 tünder
- Oder 1 tünder
- Kaer 4 tündrit
- Nisu 2 külimittu
- Humalad 10 naela
- Töö (teotöö) raha 3 hõbetaalrit
- Ratsaniku raha 3 taalrit
Selgituseks: Saksa adramaa ehk taluadramaa keskmine normaalsuurus oli 10 ha. Poola adramaa võrdus nelja saksa adramaaga.
Ka teine teadaolev Tudulinna kirjalik mainimine jääb veel 16. sajandisse. Rootsi riik korraldas põhjaliku revisjoni oma valdustes aastail 1583-1586 ning mõnes piirkonnas ulatus see isegi 1591 aastasse. Just selle revisjoni protokollist leiamegi „Tudelinna“ nime all põhjalikumad andmed, kus muu hulgas on üles tähendatud järgmist (tõlge: Ülle Tarkiainen):
9 miili linnusest (lossist) asub Tudulinna – 10 adramaad, liivane põllumaa, kuhu võib külvata 12 tündrit, väike heinamaa, mis paikneb kahe väikese miili kaugusel Peipsist suures metsas.
Hea palgi- ja põletuspuu mets, hea asukoht, mis sobib saeveski rajamiseks, hea haugi kalastuskoht kevadel, seda kasutab loss.
Küla keskel on tühi veski, ei ole köögiviljaaedu, on häid humalaaedu, hea karjamaa.
Need allpool nimetatud maksavad teotöö asemel raha, igaüks 3 taalrit 4 ööri.
Sel aastal, 1591, pärast venelaste rüüstamisi, ei ole maksnud rohkem kui 6 taalrit 2 ööri.
Tasub tähele panna, et nn rootsi miil oli umbes 10 km pikkune, mitte meile rohkem tuttav inglise miil. Arvestades tolleaegseid (olematuid) teid ja mõõtmistäpsust, ei tasu kaugustele antud protokolli kontekstis suurt tähelepanu pöörata.
Samast leiame vanima praeguseks teadaoleva tudulinlaste nimekirja:
- Janus Cubias – 1 adramaa, 1 hobune, 3 härga, 2 lehma
- Reino Janipoick – 1 adramaa, 1 hobune, 2 härga, 2 lehma
- Kauste Hannus – ½ adramaad, 1 hobune, 0 härga, 1 lehm
- Kallo Petter – ½ adramaad, 1 hobune, 2 härga, 2 lehma
- Nummo Hanso – ½ adramaad, 1 hobune, 2 härga, 1 lehm
Kirja on pandud veel põhjalik nimekiri mitmesugustest maksudest (vakuraha, teotöö raha jms), kümnisest (rukis, oder jne), aga ka meest ja „lossile“ ehk mõisale kogutavatest halgudest jne.
Nii 1583. kui 1591. aasta dokumentide koopiad on Tudulinnas näha nii rahvamajas kui ka kogukonnamajas (endine koolimaja) ja neid näidatakse ka suurematel festivalidel.
Järgmised teadaolevad kirjalikud allikad Tudulinna kohta pärinevad juba 17. sajandist.