社伝によれば欽明天皇元年（540）の創建。御祭神・建速須佐之男大神が対馬から来臨したため、津島と称するようになったという。弘仁元年（810）神階正一位と日本総社の号を、正暦年間（990〜95）天王社の号を賜ったと伝えられる。全国に約３千社あるという天王社の総本社を称する。
古くから津島御師の活躍により、各地に津島牛頭天王の信仰が広まった。また武門の崇敬篤く、特に勝幡城を本拠とした織田氏（弾正忠家）は当社を氏神と仰ぎ、織田信長は社殿の造営などに尽力している。織田氏の家紋は津島神社と同じ木瓜紋である。豊臣氏や徳川氏も社領の寄進や社殿の造営などを行っている。
国の重要文化財に指定されている楼門は天正19年（1591）豊臣秀吉の寄進と伝えられる。南門は慶長３年（1598）秀吉の病気平癒を祈願して豊臣秀頼が寄進したものである。本殿は慶長10年（1605）松平忠吉の妻女から寄進されたもの。
正保４年（1647）には尾張藩主・徳川義直は社領1293石を寄進、これは後に４代将軍・徳川家綱の朱印状により幕府寄進の神領となった。また、光格天皇以降、朝廷内々の御沙汰により皇族方の祈祷を申しつけられたという。
明治６年（1873）県社に列格、大正15年（1926）国幣小社に昇格。
当社の神事や祭事は数多いが、中でも７月に行われる天王祭は名高く、大阪天満宮の天神祭、厳島神社の管弦祭とともに日本三大川祭の一つに数えられる。織田信長も天王祭を見物したという記録が残り、藩政時代は尾張藩の藩祭として庇護を受けた。
宵祭には多数の提灯をつけた５艘の巻藁船が津島楽を奏しながら天王川を漕ぎ渡る。翌日の朝祭には、能人形が飾られた６艘の車楽船が楽を奏しつつ漕ぎ渡る優雅な祭礼である。
この祭の中核が「神葭流し神事」である。本殿内陣に１年間安置されていた神葭が新しい神葭に取り替えられ、旧い神葭は天王川に放流される。現在、天王川は丸池になっているが、かつては木曽川に流れ込んでおり、流された神葭が流れ着いた場所では、神葭を祀って祭が執り行うという疫病・厄難消除の神事である。
