Am 23. Oktober 1868 heiratete Madsen in Gerslev Albertine Henriette Petersen (1838–1919), Tochter des Gemeindepfarrers Jens Christian Petersen (1800–1895) und dessen Gattin Marie Kirstine Petersen, geb. Jespersen (1814–1900).