Kellum, born in Hempstead, Long Island, was trained as a carpenter; he was largely self-taught in architecture, and was taken into partnership in 1846 by the well-established New York architect Gamaliel King.
King was engaged in constructing Brooklyn City Hall, and Kellum, as junior partner, was his on-site supervisor.
Kellum designed and built for Stewart the Working Women's Hotel (1869–75, demolished), on Park Avenue between 32nd and 33rd Streets.
Kellum was also the primary architect[6] of the New York County Courthouse (1861 onwards; completed with revised and elaborated interiors, 1881), on Chambers Street behind New York City Hall; it is known as the "Tweed Courthouse" after William Marcy "Boss" Tweed, who commissioned it and profited from kickbacks during its construction.
Kellum's exterior is in the Italianate manner; immense cast-iron structural and decorative elements are to be seen in the public spaces of the rich interiors.