建国神話である『古事記』では、最初に生まれた島々の1つとして「津島」と記されている。また『日本書紀』には「対馬洲」「対馬島」と記されている（国生み）。
対馬島は古くから大陸との交流があり、歴史的に朝鮮半島に近い地理的関係から両国の中継地として日本と大陸との接点となった。
魏志倭人伝（正式には三国志・魏書・東夷伝・倭人条）には倭の一国として倭国の北岸の「狗邪韓国」の次に「対馬国」として登場する。対馬国は邪馬台国に属しており、他の倭の国にも見られる卑狗（ヒコ）という大官と、卑奴母離（ヒナモリ）という副官が置かれ統治していた。そこには千余戸が有り、人々は海産物を採集し、南北に交易を行って生活したと記されている。
古墳時代初期に築かれた出居塚古墳は前方後円墳で、有茎柳葉式銅鏃、管玉、鉄剣部分等が出土。前方後円墳は大和地方で発達した古墳の形態で、出土した有茎柳葉式銅鏃は、古式畿内型古墳の典型的出土品であり、この時代にすでに対馬は大和朝廷の強い影響下にあったことを示している。島の首長について『先代旧事本紀』の「国造本紀」に津島県直とある。古墳時代は大和朝廷が度々朝鮮半島に出兵し交戦を繰り返した時代といえる。こうした状況は『日本書紀』、『広開土王碑文』、『宋書』倭国伝、『三国史記』の記載により知る事ができる。中でも特に対馬の地名が具体的に登場するのは、日本側の記録としては『日本書紀』に、対馬北端の和珥津（わにのつ 現在の鰐浦）から出航した神功皇后率いる大軍が新羅を攻め、服属させた上、屯倉を設置したと書かれてある。また、朝鮮半島側の記録としては、『三国史記』に、第十八代・新羅王・実聖尼師今・治世七年（408年）、倭人が新羅を襲撃するために、対馬に軍営を設置し軍備を整えていた事が書かれている。このように対馬は大和朝廷による朝鮮半島出兵の中継地として重要な役割を担っていた。
663年の白村江の戦い以後、倭国は、唐・新羅の侵攻に備え、664年、対馬に防人（さきもり）が置かれ、烽火（とぶひ）が8ヶ所設置される。防人は東国から徴発された。667年には浅茅湾南岸に金田城を築いて国境要塞となる。このため国府や、多くの神社などがおかれていた。674年 厳原（いづはら）に国府を置く。674年 対馬国司守忍海造大国（おしみのみやつこのおおくに）が対馬で産出した銀を朝廷に献上。これが日本で初めての銀の産出となる。 この対馬銀山は含銀方鉛鉱の鉱床で、鉱石を山上に運び数日間焼き続けることにより残った銀を採取した。この冶金法は灰吹法に類似する。701年対馬で産出したと称する金を朝廷に献上したところ、これを慶んだ朝廷によって日本最初の元号「大宝」が建てられた。741年聖武天皇の国分寺建立の詔により対馬国分寺建立。
平安時代には、894年新羅の賊船大小100、約2,500人が佐須浦（さすうら）に攻めてくるが撃退する。1019年正体不明の賊船50隻が対馬を襲撃。記録されているだけで殺害された者365名、拉致された者1,289名で、有名な対馬銀鉱も焼損した。のちに賊の正体が刀伊（女真族）であることが判明し、刀伊の入寇と呼ばれるようになる。
12世紀には宗氏の始祖・惟宗（これむね）氏が対馬に入国する。惟宗氏は、元々太宰府の官人であったが、筑前の宗像郡から対馬に来た。1196年宗家の始祖・惟宗氏の名前が、対馬の在庁官人の中に初めて見られる。対馬守護・地頭の少弐氏の代官として次第に島での実権を握り、武士化する。それまで対馬では阿比留（あびる）氏が勢力を持っていた。阿比留氏は当時国交がなかった高麗と交易を行っていた。太宰府は咎めたが、従わなかったため、1246年大宰府の命により惟宗重尚（これむねしげひさ）が、鶏知（けち、美津島町）を中心に強い勢力を持っていた阿比留在庁（平太郎）を征討し対馬の支配を確立する。
鎌倉時代には、2度に渡る元（モンゴル帝国）とその属国高麗による日本への侵略（元寇）を受ける。対馬はその最初の攻撃目標となり、受難の時を迎える事となった。1274年蒙古兵25,000人、高麗兵8,000人及び水夫等6,700人は、高麗が建造した艦船900隻に分乗し、10月5日佐須浦に殺到する。この大軍に対し宗助国は一族郎党80余騎を率い果敢に迎撃する。しかし兵力の差は如何ともし難く、勇戦及ばず玉砕した。『日蓮聖人註画讃』によると、上陸した蒙古・高麗軍は、男を殺戮あるいは捕らえ、女は一ヶ所に集め、手に穴を開け、紐で連結し、船に結わえ付たという。これが文永の役である。1281年に二度目の日本への侵略弘安の役が起こる。元・高麗軍の陣容は、東路軍（合浦→現在の馬山市より侵攻）蒙古兵15,000人、高麗兵10,000人、水夫等17,000人。江南軍（寧波より侵攻）旧南宋兵100,000人。弘安の役においても残虐行為は再び繰り返された。『八幡愚童記』正応本には、《其中に高麗の兵船四五百艘、壱岐対馬より上りて。見かくる者を打ころしらうせきす、国民ささへかねて、妻子を引具し深山に逃かくれにけり、さるに赤子の泣こえを聞つけて、捜りもとめて捕けり。》と記されている。
元寇終結後倭寇の活動が激しくなり、対馬は倭寇の根拠地の一つとなっていた。1366年高麗が倭寇と海寇の取締を要請すると、宗経茂はこれに答え高麗との通交が始まるが、1389年、慶尚道元帥朴ウィに率いられた高麗軍が、激化していた倭寇討伐のために対馬に来襲。倭寇船300余隻を撃破し、捕虜となっていた多数の高麗人を救出した。
朝鮮半島で高麗に変わり李氏朝鮮が成立すると、宗氏は引き続き李氏朝鮮と通交するが、1419年6月倭寇征伐を大義名分とした応永の外寇が起こる。