Verheijen maakte deel uit van de sterke lichting die midden jaren '60 debuteerde, waarvan ook Ard Schenk, Kees Verkerk, Jan Bols en Peter Nottet deel uitmaakten. Ondanks die zware concurrentie haalde Verheijen een aantal keren een internationaal erepodium; in 1972 werd hij op het WK in Oslo derde op de 1500 en 5000 meter. In het eindklassement eindigde hij toen op de vijfde plaats. Ook was hij tweemaal derde op een Nederlands kampioenschap allround. In 1972 deed Verheijen mee aan de Olympische Winterspelen. Hij werd 19e op de 1500 meter en 25e op 500 meter (hij was op de 500 meter de beste Nederlander). Verder haalde hij geen Olympische nominaties meer.
Na 1972 was Verheijen een van de schaatsenrijders die met Schenk en Verkerk prof werd. In profverband nam hij deel aan het EK van 1973 in Skien (7e)[1] en aan het WK 1973 in Gotenburg (8e).[2]