Terdapat dua buah legenda yang berbeza tentang asal Barcelona. Legenda yang pertama mengatakan bahawa kota ini diasaskan oleh Hercules, 400 tahun sebelum pengasasan Rom, dan dibina semula pada abad ke-3 SM oleh Hamilcar Barca dari Carthage (bapa Hannibal) yang menamainya sebagai Barcino, sempena nama keluarganya. Legenda yang kedua pula mengatakan bahawa kota ini diasaskan hanya oleh Hamilcar Barca.[1]

Pada sekitar tahun 15 SM, orang Rom membentuk semula kota itu sebagai castrum (kem tentera Rom) yang dipusatkan pada "Mons Taber", sebuah bukit berhampiran dengan dewan bandar raya sezaman (Plaça de Sant Jaume). Di bawah orang Rom, ia merupakan sebuah tanah jajahan dengan nama keluarga Faventia [2] atau nama penuhnya, Colonia Faventia Julia Augusta Pia Barcino [3] atau Colonia Julia Augusta Faventia Paterna Barcino. Mela [4] menyebut kota itu antara pekan-pekan daerah yang lain, mungkin kerana Barcelona tenggelam oleh jirannya, Tarraco (Tarragona moden). Menurut karya penulis-penulis yang kemudian, kota ini kemudian beransur-ansur menjadi penting dan kaya, dan disayangi kerana lokasi dan pelabuhannya yang unggul.[5] Kota ini mencetak duit syiling sendiri, dengan sesetengahnya dari zaman Galba masih wujud.

Sesetengah puing Rom yang penting didedahkan di bawah Plaça del Rei, pintu masuk melalui muzium bandar raya (Museu d'Història de la Ciutat), dengan perancangan grid Rom yang umum masih dapat dilihat pada hari ini dalam susun atur pusat sejarah, Barri Gòtic ("Kawasan Goth"). Sesetengah serpihan tembuk Rom telah dimasukkan ke dalam binaan gereja La Seu [6] yang dikatakan dibina pada tahun 343. Kota itu ditaklukkan oleh tentera Visigoth pada awal abad ke-5, dan oleh tentera Moor pada awal abad ke-8. Louis, anak lelaki Charlemagne, menewaskan amir Moor pada 801 dan menjadikan kota itu sebagai Marca Hispanica Carolinga, zon penimbal yang diperintah oleh count Barcelona. Ketika dijarah oleh Al-Mansur pada tahun 985, Barcelona masih merupakan sebuah wilayah perbatasan Kristian.

Para count Barcelona menjadi semakin bebas dan memperluas wilayah mereka sehingga merangkumi semua kawasan Catalonia. Kemudiannya pada abad ke-13, Kerajaan Aragon menaklukkan banyak tanah jajahan di luar negeri, dan memerintah Laut Mediterranean barat serta wilayah-wilayah yang jauh dari Naples dan Sicily sehingga Athens. Hubungan dinasti yang diikat antara Kerajaan Aragon dengan Kerajaan Castile menandakan permulaan kemerosotan Barcelona.