Keju Cheddar telah dihasilkan paling tidak sejak tahun 1170. Sebuah gulungan paip daripada [Raja Henry II]] yang berasal dari tahun 1170 memuatkan pembelian 4726.43 kg keju dengan harga satu farthing per kg (£3/ton).[4] Resep keju Cheddar konon dibawa orang Romawi ke Inggris dari daerah asal keju tersebut di Cantal, Perancis.[5] Keju Cheddar secara tradisional harus dibuat di tempat di dalam lingkungan jejari 30 batu (48 km) dari Wells Cathedral.[1]

Joseph Harding, tukang susu dari Somerset, disebut sebagai tokoh yang berjasa melakukan pemodenan dan piawaian keju Cheddar.[6] Beliau mengembangkan teknik, peningkatan standard kebersihan produk susu, dan teknik pembuatan keju moden. Disebabkan itu, Joseph Harding digelar sebagai bapa keju Cheddar.[7] Harding memperkenalkan peralatan baru dalam proses pembuatan keju, termasuk alat "pencincang berputar" untuk memotong dadih susu yang mengurangkan kerja manual.[8][9] "Kaedah Joseph Harding" adalah sistem pembuatan keju Cheddar moden yang pertama kali menggunakan prinsip-prinsip saintifik. Harding menyatakan bahawa "keju Cheddar bukan dibuat di ladang, bukan di kandang lembu, atau bukan juga di dalam lembu, namun dibuat di tempat pemprosesan susu.[10] Beliau dan isterinya adalah orang yang berperanan dalam pengenalan keju ke Scotland dan Amerika Utara. Henry Harding, anak Joseph Harding, juga memperkenalkan pembuatan keju ke Australia.[11]

Semasa Perang Dunia II, sebahagian besar susu di England digunakan untuk pembuatan sejenis keju yang dinamakan "Cheddar Kerajaan" untuk dibahagi-bahagikan sebagai catuan makanan pada zaman perang.[12] Pembuatan keju "Cheddar Kerajaan" hampir-hampir menjadikan pengeluar keju lain muflis di England. Sebelum Perang Dunia I, di England terdapat lebih daripada 3,500 pengeluar keju, namun tidak lebih dari 100 pengeluar yang tinggal selepas Perang Dunia II.[13]

Pada Julai 2009, gabungan pengeluar keju "West Country Farmhouse" melancarkan sepotong keju Cheddar ke sempadan angkasa (100 km di atas permukaan laut).[14] Walaupun hubungan GPS dengan kenderaan angkasa (belon udara) hilang, keju itu kemudiannya ditemui dalam keadaan baik.