Kata tembakau berasal dari kata "tabaco" dalam Bahasa Spanyol.[3] Akan tetapi asal usul dari kata "tabaco" masih merupakan perdebatan di kalangan pakar etnomologi.[4] Kata ini diperkirakan merupakan kata serapan dalam Bahasa Guarani, yaitu yang mengacu pada tabung yang digunakan untuk menghisap bubuk tembakau yang digunakan oleh Suku Indian Haiti dan terbuat dari tulang tapir.[5] Pendapat ini sesuai dengan pernyataan Gonzalo Fernández de Oviedo y Valdés yang mengatakan bahwa "tabaco" merupakan sejenis pipa berbentuk huruf Y untuk menghirup asap tembakau, sedangkan daun-daun tembakau yang digunakan dirujuk sebagai cohiba. Pendapat lain oleh Bartolomé de las Casas juga menyatakan bahwa pada saat Kristoforus Kolumbus mengirimkan Luís Vaz de Torres dalam perjalanan menemui Kaisar Tiongkok. Dia salah mendarat dan bertemu dengan suku Indian yang menggulung daun tembakau. Mereka menyebut daun tersebut sebagai "cohiba" atau "cojiba" dan menggulung daun tersebut untuk membuat "tabaco" sebagai rokok yang dimasukkan di hidung untuk dihirup asapnya.[6]

Budidaya tembakau diperkirakan telah berlangsung sejak 6.000 SM.[13] Tumbuhan tembakau merupakan tumbuhan asli dari Amerika Selatan dan Amerika Utara. Berdasarkan kajian arkeologi, tembakau pertama kali digunakan pada abad 1 SM oleh Bangsa Maya dari Amerika Tengah sebagai rokok untuk kegiatan upacara keagamaan. Kebiasaan ini menyebar hingga Lembah Missisipi saat Bangsa Maya bermigrasi ke arah selatan Amerika antara 470 dan 630 SM sehingga diikuti oleh suku asli tetangga lokasi mereka tinggal.[14] Berdasarkan penuturan Diego de Landa, tembakau biasa digunakan oleh Bangsa Maya untuk ritual pubertas dengan memerintahkan para anak laki-laki dan perempuan untuk menelan(chupar) asap (humazo) yang diperintahkan oleh pendeta.[15] Selain untuk kegiatan keagamaan, Masyarakat Adat Hutan Timur Laut menggunakan tembakau sebagai alat dagang serta untuk melakukan traktat aliansi atau peperangan yang mereka bawa di sebuah kantong.[16] Bagi masyarakat adat ini, tembakau merupakan hadian dari Sang Pencipta sehingga dapat menjadi medium untuk menghantarkan doa dan fikiran ke Sang Pencipta melalui asap yang dihasilkan.[17]

Tembakau juga biasa digunakan sebagai obat analgesik untuk sakit gigi dan telinga serta sebagai tuam. Selain itu, Suku Indian di California biasa menggunakan tembakau sebagai obat demam yang biasanya dicampur dengan daun dari Salvia dorrii, atau akar dari Leptotaenia multifida.[18] Berdasarkan penuturan Francisco Javier Clavijero, Raja Suku Aztek menggunakan asap tembakau sebagai obat tidur.[19]

Sejarah tertulis tentang tembakau pertama kali ditulis oleh Kolumbus dalam jurnalnya pada tanggal 15 Oktober 1492 . Kolombus melihat seorang lelaki yang berada di atas kano membawa dedaunan kering saat berada antara Pulau Santa Maria dan Pulau Fernandina. Dedaunan tersebut, sebelumnya ia terima saat mendarat di Pulau San Salvador.[20] Kolombus menerima tembakau sebagai bentuk pertemanan oleh warga lokal saat dia mendarat di pulau tersebut pada tanggal 12 Oktober 1492, meskipun pada akhirnya Kolombus membuang tembakau tersebut.[21][22]

Penggunaan tembakau dalam kegiatan merokok pertama kali dilihat ketika Kolumbus mengirim Torres dan Rodrigo de Jerez untuk menemui Kaisar Tiongkok, tapi tidak pernah bertemu dan malah menemukan suku Indian yang sedang merokok tembakau dengan pipa yang diceritakan oleh Casas. Kedua orang tersebut kembali ke kapal dan melaporkan penemuannya kepada Kolumbus. Kolumbus menuliskan penemuan tersebut dalam jurnalnya pada tanggal 6 November 1492 bahwa dia mendapati bahwa kedua anak buahnya bertemu banyak orang yang membakar dedaunan untuk menghasilkan asap berbau harum.[23] Jerez diakui sebagai perokok Eropa pertama karena merupakan Bangsa Eropa pertama yang merokok saat dia pulang ke Ayamonte. Namun, dia ditangkap oleh Inkuisisi Spanyol karena dianggap bersekongkol dengan setan saat mengeluarkan asap dari hidung dan mulut. Akhirnya, Jerez dipenjara selama sepuluh tahun.[24]

Pada pelayaran Kolumbus yang kedua di tahun 1493, dia membawa Ramón Pané yang merupakan seorang frater yang ditugaskan untuk mencatat kebiasaan dan belajar bahasa suku Indian di Pulau Hispaniola. Berdasarkan pengalamannya ini, Pane menulis buku Relación acerca de las antigüedades de los indios. Buku ini menjadi buku pertama yang menjelaskan penggunaan tembakau oleh Suku Indian beserta sistem kepercayaan mereka.[25] Dia menulis bahwa tabib suku Indian menghirup bubuk yang memabukkan sehingga merasa kegirangan. Tabib tersebut lalu mengambil napas dan menghembuskan napasnya ke dahi, belakang mata dan leher. Setelah menghembuskan napas tersebut, tabib akan mendiagnosis bahwa pasien telah sembuh dengan menarik penyakit dari pembuluh darah pasien. Bubuk ini juga digunakan untuk membersihkan hidung dengan menaruh tongkat sepanjang satu kaki Satu ujung menampung bubuk dan satu lagi berada di lubang hidung. Bubuk ini dihirup untuk membersihkan hidung secara menyeluruh. Pane mengidentifikasi bubuk tersebut dengan nama cogioba. Cogioba merupakan tembakau hirup.[26]

Selain digunakan dengan dihirup dan dirokok, Bangsa Indian juga mengonsumsi tembakau dengan dikunyah. Amerigo Vespucci menceritakan pengalamannya ini saat berkunjung ke dunia baru. Pada tahun 1499, ia melihat bangsa Indian di di Pulau Margarita di Venezuela yang mengunyah tembakau dengan kapur untuk menghilangkan haus. Pengalaman ini tercatat dalam buku Cosmographic introductio yang diterbitkan pada tahun 1507. Kebiasaan mengunyah ini juga disaksikan oleh Pedro Alonso Niño dan Cristobal Guerra. Mereka melihat masyarakat asli Venezuela mengunyah tembakau sebagai pembersih gigi.[26] Pendaratan Bangsa Spanyol di Paraguay pada tahun 1503 juga mencatat praktik pengunyahan tembakau dan digunakan sebagai senjata. Mereka diserang oleh warga asli di sana dengan dimuncratkan kunyahan tembakau ke muka dan mengotori baju sehingga Bangsa Spanyol mundur dan meninggalkan tempat tersebut.[27]

Pada tahun 1518, penampakan tembakau dalam bentuk cerutu pertama kali dicatat oleh Juan Diaz yang merupakan seorang kapelan untuk Juan de Grijalva dalam ekspedisinya. Dia mencatat bahwa Grijalva diberikan hadiah gelagah yang mengeluarkan aroma harum ketika dibakar saat mendarat di Pulau Cozumel, pesisir Yucatan.[19] Saat menginvasi Meksiko, Hernán Cortés juga menemukan kebiasaan ini kembali pada tahun 1519.[28]

Bangsa Turk membawa tembakau dan menyebarkan di Mesir pada awal abad ke 15 dan menjadi cikal bakal penyebaran tembakau di Timur Tengah. Tembakau tiba di Tiongkok pada tahun 1530 yang diperikirakan melalui jalur Filipina atau Jepang.[30]