Zeuthen nació en Grimstrup, cerca de Varde, donde su padre era pastor.
En 1849, su padre se mudó a una iglesia en Sorø donde Zeuthen comenzó su educación secundaria.
En 1857 ingresó en la Universidad de Copenhague para estudiar matemáticas y se graduó con una maestría en 1862.
Durante 39 años fue secretario de la Real Academia Danesa de Ciencias y Letras, período durante el cual también impartió clases en el Instituto Politécnico.
Fue orador invitado en el Congreso Internacional de Matemáticos en 1897 en Zurich, en 1904 en Heidelberg y en 1908 en Roma.