Les premières traces de formes de vie dans la région sont celles de fossiles, que l'on date d'il y a 250 millions d'années.
Les premiers habitants autour de Bethulie furent les Bushmen, dont les nombreux dessins sont toujours présents dans la région. En 1828, la London Missionary Society crée une mission dédiée à l'évangélisation des San Bushman.
Le lieu était à l'origine connu sous le nom de Groot Moordenaarspoort (la passe du meurtrier), après qu'un affrontement eut lieu entre les tribus Sotho et Griqua. En 1832, le missionnaire Jean-Pierre Pellissier, l'un des premiers pionniers à construire des édifices au nord de l'Orange, remplace les missionnaires précédents.
La mission accueille aujourd'hui un musée qui présente des objets de l'époque et des informations sur la vie et l'œuvre de Jean-Pierre Pellissier, du chef Lephoi, et de son peuple. Jusqu'en 1833, Bethulie était appelée « Caledon », d'après la rivière qui coule non loin. Or, une ville de la colonie du Cap portait déjà le même nom. C'est en 1833 qu'un missionnaire français de la Paris Missionary Society prend la direction de la région et renomme la mission « Bethulua », ce qui signifie « le lieu de vénération ». En 1835, elle est renommée Verheullpolis et en 1863 se construit la ville, qui prend alors le nom d'Heidelberg.
En 1872, la ville reprend définitivement son nom de Bethulie.
Durant la seconde guerre des Boers, la ville abrite le troisième plus grand camp de concentration érigé pendant la guerre par les Britanniques.
