Menurut sejarawan Prof. Dr. Slamet Muljana, tokoh Semar pertama kali ditemukan dalam karya sastra zaman Kerajaan Majapahit berjudul Sudamala. Selain dalam bentuk kakimpoi, kisah Sudamala juga dipahat sebagai relief dalam Candi Sukuh yang berangka tahun 1439.
Semar dikisahkan sebagai abdi atau hamba tokoh utama cerita tersebut, yaitu Sahadewa dari keluarga Pandawa. Tentu saja peran Semar tidak hanya sebagai pengikut saja, melainkan juga sebagai pelontar humor untuk mencairkan suasana yang tegang.
Pada zaman berikutnya, ketika kerajaan-kerajaan Islam berkembang di Pulau Jawa, pewayangan pun dipergunakan sebagai salah satu media dakwah. Kisah-kisah yang dipentaskan masih seputar Mahabharata yang saat itu sudah melekat kuat dalam memori masyarakat Jawa. Salah satu ulama yang terkenal sebagai ahli budaya, misalnya Sunan Kalijaga. Dalam pementasan wayang, tokoh Semar masih tetap dipertahankan keberadaannya, bahkan peran aktifnya lebih banyak daripada dalam kisah Sudamala.
Dalam perkembangan selanjutnya, derajat Semar semakin meningkat lagi. Para pujangga Jawa dalam karya-karya sastra mereka mengisahkan Semar bukan sekadar rakyat jelata biasa, melainkan penjelmaan Batara Ismaya, kakak dari Batara Guru, raja para dewa.

Nama lengkap dari Gareng sebenarnya adalah Nala Gareng, hanya saja masyarakat sekarang lebih akrab dengan sebutan “Gareng”.
Gareng adalah punakawan yang berkaki pincang. Hal ini merupakan sebuah sanepa dari sifat Gareng sebagai kawula yang selalu hati-hati dalam bertindak. Selain itu, cacat fisik Gareng yang lain adalah tangan yang ciker atau patah. Ini adalah sanepa bahwa Gareng memiliki sifat tidak suka mengambil hak milik orang lain. Diceritakan bahwa tumit kanannya terkena semacam penyakit bubul.
Dalam suatu carangan Gareng pernah menjadi raja di Paranggumiwayang dengan gelar Pandu Pragola. Saat itu dia berhasil mengalahkan Prabu Welgeduwelbeh raja dari Borneo yang tidak lain adalah penjelmaan dari saudaranya sendiri yaitu Petruk.
Dulunya, Gareng berujud satria tampan bernama Bambang Sukodadi dari pedepokan Bluktiba. Gareng sangat sakti namun sombong, sehingga selalu menantang duel setiap satria yang ditemuinya. Suatu hari, saat baru saja menyelesaikan tapanya, ia berjumpa dengan satria lain bernama Bambang Panyukilan. Karena suatu kesalahpahaman, mereka malah berkelahi. Dari hasil perkelahian itu, tidak ada yang menang dan kalah, bahkan wajah mereka berdua rusak. Kemudian datanglah Batara Ismaya (Semar) yang kemudian melerai mereka. Karena Batara Ismaya ini adalah pamong para satria Pandawa yang berjalan di atas kebenaran, maka dalam bentuk Jangganan Samara Anta, dia (Ismaya) memberi nasihat kepada kedua satria yang baru saja berkelahi itu.
Karena kagum oleh nasihat Batara Ismaya, kedua satria itu minta mengabdi dan minta diaku anak oleh Lurah Karang Kadempel, titisan dewa (Batara Ismaya) itu. Akhirnya Jangganan Samara Anta bersedia menerima mereka, asal kedua satria itu mau menemani dia menjadi pamong para kesatria berbudi luhur (Pandawa), dan akhirnya mereka berdua setuju. Gareng kemudian diangkat menjadi anak tertua (sulung) dari Semar.

Menurut pedalangan, ia adalah anak pendeta raksasa di pertapaan dan bertempat di dalam laut bernama Begawan Salantara. Sebelumnya ia bernama Bambang Pecruk Panyukilan. Ia gemar bersenda gurau, baik dengan ucapan maupun tingkah laku dan senang berkelahi. Ia seorang yang pilih tanding/sakti di tempat kediamannya dan daerah sekitarnya. Oleh karena itu ia ingin berkelana guna menguji kekuatan dan kesaktiannya.
Di tengah jalan ia bertemu dengan Bambang Sukodadi dari pertapaan Bluluktiba yang pergi dari padepokannya di atas bukit, untuk mencoba kekebalannya. Karena mempunyai maksud yang sama, maka terjadilah perang tanding. Mereka berkelahi sangat lama, saling menghantam, bergumul, tarik-menarik, tendang-menendang, injak-menginjak, hingga tubuhnya menjadi cacat dan berubah sama sekali dari wujud aslinya yang tampan. Perkelahian ini kemudian dipisahkan oleh Smarasanta (Semar) dan Bagong yang mengiringi Batara Ismaya. Mereka diberi petuah dan nasihat sehingga akhirnya keduanya menyerahkan diri dan berguru kepada Smara/Semar dan mengabdi kepada Sanghyang Ismaya. Demikianlah peristiwa tersebut diceritakan dalam lakon Batara Ismaya Krama.
Karena perubahan wujud tersebut masing-masing kemudian berganti nama. Bambang Pecruk Panyukilan menjadi Petruk, sedangkan Bambang Sukodadi menjadi Gareng.

Beberapa versi menyebutkan bahwa, sesungguhnya Bagong bukan anak kandung Semar. Dikisahkan Semar merupakan penjelmaan seorang dewa bernama Batara Ismaya yang diturunkan ke dunia bersama kakaknya, yaitu Togog atau Batara Antaga untuk mengasuh keturunan adik mereka, yaitu Batara Guru.
Togog dan Semar sama-sama mengajukan permohonan kepada ayah mereka, yaitu Sanghyang Tunggal, supaya masing-masing diberi teman. Sanghyang Tunggal ganti mengajukan pertanyaan berbunyi, siapa kawan sejati manusia. Togog menjawab "hasrat", sedangkan Semar menjawab "bayangan". Dari jawaban tersebut, Sanghyang Tunggal pun mencipta hasrat Togog menjadi manusia kerdil bernama Bilung, sedangkan bayangan Semar dicipta menjadi manusia bertubuh bulat, bernama Bagong.
Versi lain menyebutkan, Semar adalah cucu Batara Ismaya. Semar mengabdi kepada seorang pertapa bernama Resi Manumanasa yang kelak menjadi leluhur para Pandawa. Ketika Manumanasa hendak mencapai moksha, Semar merasa kesepian dan meminta diberi teman. Manumanasa menjawab bahwa temannya yang paling setia adalah bayangannya sendiri. Seketika itu pula, bayangan Semar pun berubah menjadi manusia, dan diberi nama Bagong.