Basilika ini dibangun pada tahun 1087 sampai 1197, pada masa dominasi Italo-Norman di Puglia, suatu kawasan yang dulu pernah menjadi bagian dari Katapan Bizantium, di mana Bari sebagai ibu kotanya. Pendiriannya berhubungan dengan pencurian relikwi Santo Nikolaus dari situs aslinya di Myra, kini bagian dari Turki. Ketika Myra dikuasai oleh Saracen, beberapa pihak melihat ini sebagai peluang untuk memindahkan relikwi sang santo ke lokasi yang lebih aman. Menurut legenda yang terjustifikasi, sang santo, meninggalkan kota ini pada perjalanannya menuju Roma, dan dia memilih Bari sebagai tempat peristirahatan terakhirnya. Ada persaingan yang besar relikwi-relikwi antara Venesia dan Bari. Bari-lah pemenangnya, relikwi diangkut di bawah perlindungan wali Yunani dan guru-guru Muslim, dan pada 9 Mei 1087, dan mendarat dengan selamat di Bari. Sebuah gereja baru dibangun untuk menaungi jenazah Nikolaus dan Paus Urbanus II menghadiri konsekrasi (penyucian) ruang bawah tanah gereja ini pada tahun 1089. Gedung ini secara resmi dikonsekrasi (disucikan) pada tahun 1197, dan dihadiri oleh Vikaris Imperium, Uskup Konrad dari Hildesheim, dan berbagai uskup, wali gereja, dan orang-orang terhormat. Elias, abbasbiara terdekat yakni Santo Benediktus, dinamai sebagai Uskup Agung pertama. Katedra (takhta keuskupan) dia masih berdiri di dalam gereja ini hingga kini.
Gereja ini lebih mendekati bentuk persegi, tampak lebih cocok disebut kastil daripada gereja. Penekanan ini diperkuat oleh keberadaan dua menara yang tidak begitu massif yang menjadi kerangka fasad. Tentu saja dalam sejarahnya gereja ini pernah dipergunakan sebagai kastil sebanyak beberapa kali.
Di bagian dalam gereja terdapat sebuah ruang tengah (nave) dan dua lorong, dipisahkan oleh lajur-lajur granit dan pilaster. Pastoran terpisah dari bangunan utama, dalam artian tiga lengkungan disokong oleh lajur-lajur yang dipengaruhi gaya Bizantium. Di atas lorong terdapat galeria atau tribun yang diperuntukkan bagi jemaat perempuan, yang berhubungan langsung dan terbuka dengan ruang tengah. Basilika ini adalah gereja pertama yang menggunakan desain seperti ini, yang di kemudian hari mengilhami berbagai macam bangunan di kawasan itu.
Basilika ini menjadi rumah bagi salah satu karya seni pahat Romantik terpenting di Italia Selatan, katedra (takhta uskup) selesai dikerjakan pada penghujung abad ke-11 yang diperuntukkan bagi Elias. Terdapat beberapa trotoir mozaik yang sangat bernilai di dalam ruang bawah tanah dan pastoran. Kiborium (kubah interior di atas mimbar yang diperuntukkan bagi pembaca doa/ceramah), yang paling kuno di kawasan itu, juga dihias dengan mozaik; terdapat empat lajur/pilar dengan gambar dedaunan, binatang, dan tokoh-tokoh mitologi.
Pusara Santo Nikolaus di Bari, sebagaimana halnya yang masih terwujud saat ini.
Di dalam gereja terdapat pusara Renaisans Bona Sforza, (abad ke-16), dengan marmer. Museum Basilika memiliki karya-karya seni yang berharga, termasuk koleksi penyangga lilin dari abad ke-12 yang disumbangkan oleh Raja Carlo I dari Napoli.
Gereja ini dipugar semula pada penghujung abad ke-13, pada tahun 1456 dan pada abad ke-17. Dalam pemugaran pada abad ke-12, sebagian besar tambahan bergaya Barok dihilangkan, hanya menyisakan langit-langit kayu yang disepuh, pengerangkaan kanvas oleh Carlo De Rosa.
Masa puasa
Pencitraan Santo Nikolaus menurut sudut pandang Rusia.
Tanggal 6 Desember adalah Hari Santo Nikolaus, hari puasa utama Santo Nikolaus. Pada tanggal ini, adalah tradisi bagi kependetaan basilika untuk merendahkan labu/botol ke pusara bawah tanah Santo Nikolaus untuk mengekstraksi dupa yang diyakini memancar dari relikwi. Penampung-penampung dupa ini dikirimkan dari seluruh penjuru dunia, dan orang-orang yang percaya telah melaporkan beberapa keajaiban sebagai hasil dari perminyakan dengannya. Karena Gereja Ortodoks mengikuti Kalender Julian, 6 Desember bersamaan dengan 19 Desember Kalender Gregorian, maka sebenarnya ada dua perayaan pada satu hari raya: yang satu mengikuti kalender baru (6 Desember) dan yang lainnya mengikuti kalender lama (19 Desember). Kedua-duanya dirayakan dengan kekhidmatan yang mendalam di Bari.
9 Mei (22 Mei) dirayakan setiap tahun di Gereja Ortodoks Rusia sebagai hari puasa "Pemindahan Relikwi Santo Nikolaus dari Myra ke Bari".
Peziarah ke basilika ini dari Eropa Timur bertambah secara dramatis sejak kejatuhan Tirai Besi, tidak hanya untuk hari puasa, tetapi sepanjang tahun.
